E. Живая последовательность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Японии цифра $$$4$$$ читается как смерть, поэтому Боб решил построить живую последовательность. Живая последовательность $$$a$$$ содержит все натуральные числа, не содержащие цифры $$$4$$$. $$$a = [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, \ldots]$$$.

Например, число $$$1235$$$ входит в последовательность $$$a$$$, а числа $$$4321$$$, $$$443$$$ не входят в последовательность $$$a$$$.

Боб понял, что не умеет быстро искать конкретное число по позиции $$$k$$$ в последовательности, поэтому просит вас о помощи.

Например, если Боб хочет узнать число на позиции $$$k = 4$$$ (индексация с $$$1$$$), то вам нужно ответить $$$a_k = 5$$$.

Входные данные

В первой строке входных данных дано единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

В единственной строке каждого набора входных данных задано одно целое число $$$k$$$ ($$$1 \le k \le 10^{12}$$$) — позиция, интересующая Боба.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке число $$$a_k$$$ в индексации с $$$1$$$.

Пример
Входные данные
7
3
5
22
10
100
12345
827264634912
Выходные данные
3
6
25
11
121
18937
2932285320890