Đăng rất ghét những số nguyên dương chia hết cho \(3\) và những số có chữ số tận cùng bằng \(3\). Những số có cả hai yếu tố trên, Đăng càng ghét đậm hơn.

Đăng bắt đầu viết một dãy số (bắt đầu từ \(1\)) chỉ bao gồm các số mà Đăng thích là \(1,2,4,5,7,8,10,11,...\).

Yêu cầu: In ra số thứ \(k\) trong dãy trên.

Input

• Dòng đầu ghi số \(q\) \((q < 101)\) - số câu hỏi.
• \(q\) block tiếp theo, mỗi block nhập số \(k\), mỗi số trên \(1\) dòng. \((k \le 1000)\)

Output

• Ứng với mỗi câu hỏi, in ra kết quả tương ứng.

Example

10
1
2
3
4
5
6
7
8
9
1000

1
2
4
5
7
8
10
11
14
1666