题目描述

将大于 0 的整数写成一排组成一个无限长的数，即：12345678910111213141516....问这个数的第 n 位的数字是什么？**

输入格式

第一行：1 个数 T 表示询问的数量（2≤T≤100000）。 第 2 至 n+1 行：每行 1 个数，对应询问的 n 。（1≤n≤10^9）

输出格式

输出共 t 行，对应 t 次询问的答案。

样例

输入

3
3
10
21

输出

3
1
5

提示

【数据范围】**

对于 4%的数据，2≤T≤10，1≤n≤100；

对于 40%的数据，2≤T≤500，1≤n≤50000；

对于 100%的数据，2≤T≤100000，1≤n≤10^9；

来源

CodesOnline