You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

夏雨忽如雪，凉意沁心扉。

情在炎炎日，爱在纷纷飞。

相依无怨悔，共度每朝晖。

雪融雨中泪，永伴不言归。

题目描述

小 T 想送给小 Z 一个叫做『夏雨雪』的字符序列。在小 T 和 小 Z 居住的地方，夏天降雪永远不会发生，这个序列也是无穷无尽的。

这个『夏雨雪』序列是由所有正整数拼接而成的。也就是形如 $12345678910111213141516\dots$。

由于小 T 要和小 Z 度过一生一世，所以他不会一次性把一整个『夏雨雪』序列送给小 Z，而是每次送一个序列中的字符。

小 T 这一次想送给小 Z 一共 $T$ 个字符。每一次都会问你这个序列的第 $k$ 个字符是什么。

雨：动词，降，名词活用作动词。

输入格式

第一行一个整数 $T$ 表示本测试点的测试数据个数。满足 $1\leq T \leq 5\times 10^4$。

接下来有 $T$ 组测试数据。

• 每组测试数据第一行是一个整数 $k$ 表示问你的这个序列第 $k$ 个字符是什么。满足 $1\leq k\leq 10^{12}$。

输出格式

对于每组测试数据，告诉小 T 一个字符表示这个序列的第 $k$ 个字符是什么。

3
1
7
21

1
7
5

提示

对于 $40\%$ 的数据，满足 $1\leq k\leq 10^3$；

对于 $60\%$ 的数据，满足 $1\leq k\leq 10^6$；

对于 $100\%$ 的数据，满足 $1\leq k\leq 10^{12}$，$1\leq T\leq 5\times 10^4$。

注意本题并没有对 $\sum k$ 做出约束。