Розглянемо нескінченний рядок, який складається з усіх натуральних чисел у порядку зростання: 12345678910111213141516171819202122232425...

Ваше завдання — обробити ~q~ запитів виду: яка цифра стоїть на позиції ~k~ у рядку?

Обмеження

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

Формат вхідних даних

Перший рядок містить ціле число ~q~: кількість запитів.

Після цього є ~q~ рядків, які описують запити. У кожному рядку є ціле число ~k~: позиція з індексом 1 у рядку.

Формат вихідних даних

Для кожного запиту виведіть відповідну цифру.

Приклад вхідних даних

3
7
19
12

Приклад вихідних даних

7
4
1