A3165. 超级字符串
编程题
普及+/提高
知识点
题目描述
Macw 在无数次 $\mathtt{oi}$ 竞赛的狱炼之后，悟出一个真理，往往越容易的题目，陷阱越深。由此，Macw 创作了这道题目。
Macw 首先给出两个短串
（１）
（２）
请你编程找出这个长串的第 $N$ 个字符。
Problem credits: [Macw07](https://www.acgo.cn/person/929871)。
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](https://www.acgo.cn/person/929871)。
输入格式
本题每个测试点有 $T$ 个测试样例。
第一行输入一个整数 $T$，代表测试用例的个数。
接下来的 $T$ 行，每一行一个整数 $N_i$，表示需要求的解。
第一行输入一个整数 $T$，代表测试用例的个数。
接下来的 $T$ 行，每一行一个整数 $N_i$，表示需要求的解。
输出格式
对于每一个 $N_i$，求出长串的第 $N_i$ 个字符。
输入输出样例
输入 #1
5 10 27 36 55 85
输出 #1
3 3 2 1 4
说明/提示
**数据范围约定：**
对于 $40\%$ 的数据，满足 $1\le n, T \le 1005$。
对于 $100\%$ 的数据，保证 $1\le T \le 10^5$。
对于 $100\%$ 的数据，保证 $1 \le N_i \le 10^9$。
对于 $40\%$ 的数据，满足 $1\le n, T \le 1005$。
对于 $100\%$ 的数据，保证 $1\le T \le 10^5$。
对于 $100\%$ 的数据，保证 $1 \le N_i \le 10^9$。