← 返回题目列表

Codeforces · 1811/E

E. 生活序列

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

在日本,数字 $$$4$$$ 读起来就像死亡,所以鲍勃决定建立一个现场序列。生存序列 $$$a$$$ 包含所有不包含数字 $$$4$$$ 的自然数。 $$$a = [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, \点]$$$。

例如,数字 $$$1235$$$ 是序列 $$$a$$$ 的一部分,但数字 $$$4321$$$、$$$443$$$ 不是序列 $$$a$$$ 的一部分。

Bob 意识到他不知道如何通过序列中 $$$k$$$ 的位置快速搜索特定号码,因此他请求您的帮助。

例如,如果 Bob 想查找位置 $$$k = 4$$$ 处的数字(从 $$$1$$$ 开始索引),则需要回答 $$$a_k = 5$$$。

输入

输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

在每个测试用例的唯一行中,有一个整数 $$$k$$$ ($$$1 \le k \le 10^{12}$$$) — Bob 感兴趣的位置。

输出

对于每个测试用例,在单独的行上打印数字 $$$a_k$$$,并使用 $$$1$$$ 进行索引。

示例

输入 #1

7
3
5
22
10
100
12345
827264634912

输出 #1

3
6
25
11
121
18937
2932285320890