A29216.超级字符串

Macw 在无数次 $\mathtt{oi}$ 竞赛的狱炼之后，悟出一个真理，往往越容易的题目，陷阱越深。由此，Macw 创作了这道题目。

Macw 首先给出两个短串 A=4567 (4个字符)， B=123 (3个字符)。反复进行如下的操作得到一个长串 C。

（１）C=B+A (例如：A=4567, B=123, C=B+A=1234567)

（２）A=B; B=C (上述例子 A=123, B=1234567)

请你编程找出这个长串的第 $N$ 个字符。

Problem credits: Macw07。

本题每个测试点有 $T$ 个测试样例。

第一行输入一个整数 $T$，代表测试用例的个数。
接下来的 $T$ 行，每一行一个整数 $N_i$，表示需要求的解。

对于每一个 $N_i$，求出长串的第 $N_i$ 个字符。

数据范围约定：
对于 $40\%$ 的数据，满足 $1\le n, T \le 1005$。
对于 $100\%$ 的数据，保证 $1\le T \le 10^5$。
对于 $100\%$ 的数据，保证 $1 \le N_i \le 10^9$。