Description

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

Input Format

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

Output Format

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

3
3
10
21

3
1
5

Hint

【数据范围】

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

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

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

Source

CodesOnline