Polycarp 不喜欢可被 $$$3$$$ 整除的整数或以十进制表示形式以数字 $$$3$$$ 结尾的整数。波利卡普也不喜欢满足这两个条件的整数。
Polycarp 开始写出他喜欢的正整数(大于 $$$0$$$):$$$1, 2, 4, 5, 7, 8, 10, 11, 14, 16, \dots$$$。输出该序列的第 $$$k$$$ 个元素(元素从 $$$1$$$ 开始编号)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例由一行组成,其中包含一个整数 $$$k$$$ ($$$1 \le k \le 1000$$$)。
输出
对于每个测试用例,在单独的行中输出一个整数 $$$x$$$ — 由 Polycarp 写出的序列的第 $$$k$$$ 个元素。
示例
输入 #1
10 1 2 3 4 5 6 7 8 9 1000
输出 #1
1 2 4 5 7 8 10 11 14 1666