题目描述

考虑一个由所有正整数按照递增顺序组成的无限字符串：12345678910111213141516171819202122232425...。

你的任务是处理 $q$ 次询问，每次询问会查询字符串第 $k$ 个字符是什么数字。本题字符串编号从 $1$ 开始。

输入格式

第一行输入一个正整数 $q$ 表示询问次数。

接下来有 $q$ 行，每行输入一个整数 $k$ 表示查询。

输出格式

对于每次查询，输出一个数字字符表示答案。

样例

3
7
19
12

7
4
1

数据范围

• $1 \le q \le 1000$
• $1 \le k \le 10^{18}$