E2. Числовая последовательность (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между простой и сложной версиями — максимальное значение $$$k$$$.

Вам задана бесконечная последовательность вида «112123123412345$$$\dots$$$», в которой следуют блоки всех последовательных целых чисел, записанных друг за другом. Первый блок содержит все числа от $$$1$$$ до $$$1$$$, второй — от $$$1$$$ до $$$2$$$, третий — от $$$1$$$ до $$$3$$$, $$$\dots$$$, $$$i$$$-й блок содержит все числа от $$$1$$$ до $$$i$$$.

Таким образом, первые $$$56$$$ элементов последовательности равны «11212312341234512345612345671234567812345678912345678910». Элементы последовательности нумеруются с единицы. Например, $$$1$$$-й элемент последовательности равен $$$1$$$, $$$3$$$-й элемент последовательности равен $$$2$$$, $$$20$$$-й элемент последовательности равен $$$5$$$, $$$38$$$-й элемент равен $$$2$$$, $$$56$$$-й элемент последовательности равен $$$0$$$.

Перед вами стоит задача ответить на $$$q$$$ независимых запросов. Для $$$i$$$-го запроса задано целое число $$$k_i$$$. Определите элемент последовательности, который находится в позиции $$$k_i$$$.

Входные данные

В первой строке следует целое число $$$q$$$ ($$$1 \le q \le 500$$$) — количество запросов.

В $$$i$$$-й из следующих $$$q$$$ строк следует целое число $$$k_i$$$ $$$(1 \le k_i \le 10^{18})$$$ — описание очередного запроса.

Выходные данные

Выведите $$$q$$$ строк. В $$$i$$$-ю строку должна быть выведена цифра $$$x_i$$$ $$$(0 \le x_i \le 9)$$$ — ответ на запрос номер $$$i$$$, то есть $$$x_i$$$ должно быть равно элементу последовательности, который находится в позиции $$$k_i$$$.

Примеры
Входные данные
5
1
3
20
38
56
Выходные данные
1
2
5
2
0
Входные данные
4
2132
506
999999999999999999
1000000000000000000
Выходные данные
8
2
4
1
Примечание

Ответы на запросы из первого примера подробно разобраны в условии.