题目描述

Polycarp 不喜欢能被 $3$ 整除或者十进制表示中以 $3$ 结尾的整数。对于同时满足这两个条件的整数，Polycarp 也不喜欢。

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$ 个元素。

说明/提示

由 ChatGPT 4.1 翻译

样例

10
1
2
3
4
5
6
7
8
9
1000

1
2
4
5
7
8
10
11
14
1666