Un superstring este un șir infinit format din numere naturale nenule scrise fără spații între ele, începând cu $1$: $1223334444\dots1010\dots$ (fiecare număr $x$ apare de exact $x$ ori).

Cerință

Să se răspundă la $T$ întrebări de forma: Ce cifră se află în superstring pe poziția $k$?

Date de intrare

Fișierul de intrare superstring.in conține pe prima linie numărul de teste $T$. Pe următoarele $T$ linii se află un singur număr natural $k$ , aferent întrebării curente.

Date de ieșire

Fișierul de ieșire superstring.out conține $T$ linii, pe linia $i$ aflându-se răspunsul pentru întrebarea $i$ din fișierul de intrare.

Restricții și precizări

• $1 \leq T \leq 31 \ 000$
• $1 \leq k \leq 10^{15}$
• Pozițiile cifrelor din superstring sunt numerotate începând cu 1
• Pentru 15% dintre teste $T$, $k \leq 5 \ 000$
• Pentru alte 35% dintre teste $k \leq 10^{6}$

Exemplu

superstring.in

4
1
3
46
47

superstring.out

1
2
1
0