简单版本和困难版本之间的唯一区别是 $$$k$$$ 的最大值。
给你一个形式为“112123123412345$$$\dots$$$”的无限序列,它由依次写入的所有连续正整数块组成。第一个块包含从 $$$1$$$ 到 $$$1$$$ 的所有数字,第二个块 — 从 $$$1$$$ 到 $$$2$$$,第三块 — 从 $$$1$$$ 到 $$$3$$$、$$$\dots$$$,第 $$$i$$$ 块包含从 $$$1$$$ 到 $$$i$$$ 的所有数字。
因此序列的前 $$$56$$$ 元素是“11212312341234512345612345671234567812345678912345678910”。序列的元素从 1 开始编号。例如,序列的第 $$$1$$$-st 元素是 $$$1$$$,序列的 $$$3$$$-rd 元素是 $$$2$$$,序列的第 $$$20$$$-th 元素是 $$$5$$$,序列的第 $$$38$$$-th 元素是 $$$2$$$,序列的第 $$$56$$$-th 元素是$$$0$$$。
您的任务是回答 $$$q$$$ 独立查询。在第 $$$i$$$ 查询中,您将获得一个整数 $$$k_i$$$。计算序列中$$$k_i$$$位置处的数字。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 500$$$) — 查询数。
以下 $$$q$$$ 行中的第 $$$i$$$ 行包含一个整数 $$$k_i$$$ $$$(1 \le k_i \le 10^{18})$$$ — 相应查询的描述。
输出
打印 $$$q$$$ 行。在第 $$$i$$$ 行中打印一位数字 $$$x_i$$$ $$$(0 \le x_i \le 9)$$$ — 查询 $$$i$$$ 的答案,即 $$$x_i$$$ 应等于序列中 $$$k_i$$$ 位置的元素。
示例
输入 #1
5 1 3 20 38 56
输出 #1
1 2 5 2 0
输入 #2
4 2132 506 999999999999999999 1000000000000000000
输出 #2
8 2 4 1
注意
第一个示例的查询答案在问题陈述中进行了描述。