解题思路

把一个正整数判为“喜欢”，需要同时满足两个条件：

1. 不能被$3$整除；
2. 十进制表示中不能出现数字$3$。

题目要求按升序求第$k$个这样的数。由于$k$最大到$10^{18}$，显然不能暴力枚举。

题目内容

$TK$ 不喜欢能被 $3$ 整除的正整数，也不喜欢十进制表示中包含数字 $3$ 的正整数。

现在他要将所有他喜欢的正整数按升序排成一个序列。

给定正整数 $k$，请你找出这个序列的第 $k$ 个数。

友情提醒：第 $10^{18}+1$项为 $10\ 995\ 467\ 216\ 611\ 448\ 857$。

输入描述

第一行输入一个整数 $t(1≤t≤10^4)$,表示测试用例的数量:

接下来 $t$ 行，每行输入一个整数 $k(1≤k≤10^{18})$，表示要找的第 $k$ 个喜欢的正整数的序号。

输出描述

对于每个测试用例，在一行上输出一个整数，表示所求的第 $k$ 个喜欢的正整数

样例1

输入

5
1
2
3
4
5

输出

1
2
4
5
7

说明

在这个样例中，喜欢的正整数序列的前五项为 $1,2,4,5,7$，因此对应输出分别为 $1,2,4,5,7$。