在日本,数字 $$$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