题目描述

定义函数 $\mathrm{tostring}(n)$ 表示将数字 $n$ 按照 $10$ 进制写成字符串。例如，$\mathrm{tostring}(12345)={\tt 12345}$。由此，

• 定义字符串 $S_n={\tt 1+2+3+4+\cdots}+\mathrm{tostring}(n)$；
• 定义字符串 $S_{\infin}=S_1+S_2+S_3+S_4+\cdots$

例如，$S_{\infty}$ 的前若干项为：

$$\tt 112123123412345123456123456712345678123456789123456789101234567891011\cdots $$

现在询问 $S_{\infin}$ 的第 $i$ 位是什么字符。

输入格式

第一行为正整数 $t\ (1 \le t \le 10)$，表示测试数据组数。

接下来 $t$ 行，每行一个正整数 $i\ (1 \le i \le 2^{31}-1)$，表示一次询问。

输出格式

对于每一个 $i$，输出对应位置上的数字。

2
3
8

2
2