数字查询 (Task 2431)

• 链接: https://cses.fi/problemset/task/2431
• 板块: Introductory Problems
• 时限: 1.00 s ｜ 内存: 512 MB

描述

考虑一个由所有正整数按递增顺序拼接而成的无限长字符串： $12345678910111213141516171819202122232425\ldots$ 你需要处理 $q$ 个形如“字符串中第 $k$ 个位置上的数字是几”的查询。

输入

第一行输入包含一个整数 $q$：查询的数量。 随后有 $q$ 行描述这些查询。每行包含一个整数 $k$：字符串中从 1 开始计数的位置。

输出

对于每个查询，打印对应的数字。

约束

• $1 \le q \le 1000$
• 位置满足 $1 \le k \le 10^{18}$

样例

输入：
3
7
19
12
输出：
7
4
1