310298: CF1811E. Living Sequence

E. Living Sequencetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

In Japan, the number $4$ reads like death, so Bob decided to build a live sequence. Living sequence $a$ contains all natural numbers that do not contain the digit $4$. $a = [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, \ldots]$.

For example, the number $1235$ is part of the sequence $a$, but the numbers $4321$, $443$ are not part of the sequence $a$.

Bob realized that he does not know how to quickly search for a particular number by the position $k$ in the sequence, so he asks for your help.

For example, if Bob wants to find the number at position $k = 4$ (indexing from $1$), you need to answer $a_k = 5$.

Input

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

In the only line of each test case, there is a single integer $k$ ($1 \le k \le 10^{12}$) — the position Bob is interested in.

Output

For each test case, print on a separate line the number $a_k$ in indexing with $1$.

ExampleInput

7
3
5
22
10
100
12345
827264634912

Output

3
6
25
11
121
18937
2932285320890

题目大意：
这个问题是关于一个“活着的序列”a，这个序列包含了所有不包含数字4的自然数。例如，序列a是[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, ...]。在这个序列中，数字1235是序列的一部分，但是4321和443不是。问题是，对于给定的位置k（从1开始索引），找出序列中第k个位置的数字a_k。

输入数据格式：
输入数据的第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。每个测试用例包含一个整数k（1 ≤ k ≤ 10^12），表示Bob感兴趣的位置。

输出数据格式：
对于每个测试用例，输出一行，包含序列中第k个位置的数字a_k。

示例：
输入：
7
3
5
22
10
100
12345
827264634912

输出：
3
6
25
11
121
18937
2932285320890题目大意： 这个问题是关于一个“活着的序列”a，这个序列包含了所有不包含数字4的自然数。例如，序列a是[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, ...]。在这个序列中，数字1235是序列的一部分，但是4321和443不是。问题是，对于给定的位置k（从1开始索引），找出序列中第k个位置的数字a_k。 输入数据格式： 输入数据的第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。每个测试用例包含一个整数k（1 ≤ k ≤ 10^12），表示Bob感兴趣的位置。 输出数据格式： 对于每个测试用例，输出一行，包含序列中第k个位置的数字a_k。 示例： 输入： 7 3 5 22 10 100 12345 827264634912 输出： 3 6 25 11 121 18937 2932285320890