Considera una cadena infinita formada por todos los números enteros positivos en orden creciente:

~12345678910111213141516171819202122232425...~

Su tarea es procesar ~q~ consultas de la forma: ¿cuál es el dígito en la posición ~k~ de la cadena?

Entrada

La primera línea de entrada tiene un número entero ~q~: el número de consultas. Después, hay ~q~ líneas que describen las consultas. Cada línea tiene un número entero ~k~: una posición indexada en la cadena.

Salida

Para cada consulta, imprime el dígito correspondiente.

Restricciones

• ~1 \leq q \leq 1000~.
• ~1 \leq k \leq 10^{18}~.

Ejemplo de Entrada

3
7
19
12

Ejemplo de Salida

7
4
1