有一个无限长的数字串，它可以由如下规则生成：
初始地，令S0 = "0"。
接下来，令Si = Si - 1 + C(i) + Si - 1。其中 C(i) 表示i的个位，加号表示将两个串前后拼接。因此有：
S1 = "010"；
S2 = "0102010"；
S3 = "010201030102010"；
S4 = "0102010301020104010201030102010"；
S5 = "010201030102010401020103010201050102010301020104010201030102010"；
……
最终得到无限长的数字串。
我们约定数字串的下标从0开始用自然数连续编号。
现在给你T组询问。每组询问包含一个整数k，请你回答数字串中下标k的字符是多少。
第一行为一个整数T，表示询问数量。
接下来T行，每行为一个整数k，描述一个询问。
共T行，每行为一个整数，表示相应询问的答案。
样例输入1：
5
0
1
2
9
23
样例输入2：
5
43252898
46233378
94515561
56893392
35613355
样例输出1：
0
1
0
1
3
样例输出2：
0
0
1
0
2
