题目描述

将大于 $0$ 的整数写成一排组成一个无限长的数，即：

请问这个无限长数的第 $n$ 位数字是什么？

输入格式

第一行一个整数 $T$，表示询问的数量。

接下来 $T$ 行，每行一个整数 $n$，表示询问第 $n$ 位数字。

输出格式

输出共 $T$ 行，每行一个数字，对应每个询问的答案。

样例

3
3
10
21

3
1
5

数据范围

• 对于 $40\%$ 的数据：$2 \le T \le 10$，$1 \le n \le 100$
• 对于 $80\%$ 的数据：$2 \le T \le 500$，$1 \le n \le 50000$
• 对于 $100\%$ 的数据：$2 \le T \le 100000$，$1 \le n \le 10^9$