题目背景

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

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

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

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

题目描述

小 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$ 做出约束。