Stel dat je alle opeenvolgende natuurlijke getallen achter elkaar uitschrijft, te beginnen met het getal 1. Dan krijg je een oneindige lange rij, die op de volgende manier begint (voor de duidelijkheid zetten we hierbij spaties tussen de verschillende getallen.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 …
We bekijken deze rij echter niet als een rij van getallen, maar als een rij van cijfers. De vraag die we dan proberen te beantwoorden is wat het cijfer is dat in deze rij voorkomt op positie $$n$$. Het is bijvoorbeeld makkelijk na te gaan dat het zestiende cijfer in bovenstaande rij het cijfer 1 is. Maar wat is het cijfer op positie 2147483646?
De eerste regel van de invoer bevat een getal $$t$$ ($$1 \leq t \leq 1000$$) dat het aantal opgaven voorstelt. Daarna volgen $$t$$ opgaven. Elke opgave wordt beschreven door een regel die een getal $$k \in \mathbb{N}_0$$ ($$1 \leq k \leq 2^{31} - 1$$) bevat.
Schrijf voor elke opgave het $$k$$-de cijfer uit de rij van de natuurlijke getallen die hierboven wordt beschreven.
Tip: Indien je probeert om de rij van opeenvolgende natuurlijke getallen te genereren om daarin het juiste cijfer op te zoeken, dan zal je zeker de vooropgestelde tijdslimiet overschreiden voor grote waarden van $$k$$. Probeer daarom een slimmere oplossing te zoeken door gebruik te maken van de observatie dat de eerste 9 getallen bestaan uit 1 cijfer, de volgende 90 getallen uit 2 cijfers, de volgende 900 getallen uit 3 cijfers, enzovoort.
Invoer:
4
15
2022
1410169200
2147483646Uitvoer:
2
0
1
2