← 返回题目列表

Codeforces · 1216/E1

E1. 数字序列(简单版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是 $$$k$$$ 的最大值。

给你一个形式为“112123123412345$$$\dots$$$”的无限序列,它由依次写入的所有连续正整数块组成。第一个块包含从 $$$1$$$ 到 $$$1$$$ 的所有数字,第二个块 — 从 $$$1$$$ 到 $$$2$$$,第三块 — 从 $$$1$$$ 到 $$$3$$$、$$$\dots$$$,第 $$$i$$$ 块包含从 $$$1$$$ 到 $$$i$$$ 的所有数字。

因此序列的前 $$$56$$$ 元素是“11212312341234512345612345671234567812345678912345678910”。序列的元素从 1 开始编号。例如,序列的第 $$$1$$$-st 元素是 $$$1$$$,序列的 $$$3$$$-rd 元素是 $$$2$$$,序列的第 $$$20$$$-th 元素是 $$$5$$$,序列的第 $$$38$$$-th 元素是 $$$2$$$,序列的第 $$$56$$$-th 元素是$$$0$$$。

您的任务是回答 $$$q$$$ 独立查询。在第 $$$i$$$ 查询中,您将获得一个整数 $$$k_i$$$。计算序列中$$$k_i$$$位置处的数字。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 500$$$) — 查询数。

以下 $$$q$$$ 行中的第 $$$i$$$ 行包含一个整数 $$$k_i$$$ $$$(1 \le k_i \le 10^9)$$$ — 相应查询的描述。

输出

打印 $$$q$$$ 行。在第 $$$i$$$ 行中打印一位数字 $$$x_i$$$ $$$(0 \le x_i \le 9)$$$ — 查询 $$$i$$$ 的答案,即 $$$x_i$$$ 应等于序列中 $$$k_i$$$ 位置的元素。

示例

输入 #1

5
1
3
20
38
56

输出 #1

1
2
5
2
0

输入 #2

4
2132
506
999999999
1000000000

输出 #2

8
2
9
8

注意

第一个示例的查询答案在问题陈述中进行了描述。