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

Cerința

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 ≤ T ≤ 31000
• 1 ≤ k ≤ 1.000.000.000.000.000
• Poziţiile cifrelor din superstring sunt numerotate începând cu 1.
• Pentru 15% dintre teste T , k ≤ 5000
• Pentru alte 35% dintre teste k ≤ 1.000.000

Exemplu:

superstring.in

4
1
3
46
47

superstring.out

1
2
1
0