Polycarp 不喜欢满足以下任意条件的正整数：

1. 能被 $3$ 整除；
2. 十进制表示的最后一位是数字 $3$。

如果一个整数同时满足以上两个条件，他同样不喜欢。

Polycarp 按从小到大的顺序写下所有他喜欢的正整数序列，例如： $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$），表示查询序列的第 $k$ 个元素。

输出格式

对每个测试用例，输出一行一个整数 $x$，表示 Polycarp 写下的喜欢的整数序列中的第 $k$ 个元素。

样例输入

10
1
2
3
4
5
6
7
8
9
1000

样例输出

1
2
4
5
7
8
10
11
14
1666

说明

一个正整数 $x$ 被 Polycarp 喜欢，当且仅当：

• $x \bmod 3 \ne 0$，且
• $x$ 的十进制末位不是 $3$。