题目内容

小蓝在整理一些特殊的正整数。她认为一个正整数是「安全」的，当且仅当它既不能被 $3$ 整除，且它的十进制表示中不包含数字 $3$。现在，她将所有安全的正整数按升序排列成一个序列。对于给定的询问，请你找出这个序列中的第 $k$ 个数。

测试用例的数量 $t$ 满足 $1 \le t \le 10^4$，每个询问的序号 $k$ 满足 $1 \le k \le 10^{18}$。

输入描述

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。 接下来 $t$ 行，每行包含一个整数 $k$ ($1 \le k \le 10^{18}$)，表示要查找的序号。

输出描述

对于每个测试用例，输出一行一个整数，表示安全数列中第 $k$ 个数。

样例1

输入

1
1

输出

1

说明

对于 $k=1$，最小的安全数是 1。1 既不能被 $3$ 整除，十进制表示中也不包含数字 $3$，因此第 $1$ 个安全数就是 1。

样例2

输入

1
10

输出

16

说明

按升序排列，前 $10$ 个安全数依次为：1, 2, 4, 5, 7, 8, 10, 11, 14, 16。第 $10$ 个数是 16。

样例3

输入

3
20
25
30

输出

41
50
59

说明

安全数序列的前 $30$ 个为：1, 2, 4, 5, 7, 8, 10, 11, 14, 16, 17, 19, 20, 22, 25, 26, 28, 29, 40, 41, 44, 46, 47, 49, 50, 52, 55, 56, 58, 59。因此第 $20$ 个是 41，第 $25$ 个是 50，第 $30$ 个是 59。