Polycarp không thích các số nguyên chia hết cho 3 hay có tận cùng bằng 3 (trong biểu diễn thập phân của số). Các số thỏa mãn cả hai điều kiện, Polycarp cũng không thích.

Polycarp bắt đầu viết các số nguyên dương (lớn hơn 0) mà anh ấy thích: \(1, 2, 4, 5, 7, 8, 10, 11, 14, 16, \dots\)

Yêu cầu: Hãy in ra số thứ \(k\) trong dãy này (các số được đánh thứ tự từ 1)

Input

• Dòng đầu tiên chứa một số nguyên dương \(t\ (1 \le t \le 100)\) - số lượng bộ trường hợp cần giải quyết.
• Sau đó là \(t\) dòng, mỗi dòng chứa một số nguyên dương \(k\ (1 \le k \le 10^9)\).

Output

• Với mỗi trường hợp, in ra một dòng chứa số nguyên dương \(x\) - là số thứ \(k\) trong dãy mà Polycarp viết ra.

Example

10
1
2
3
4
5
6
7
8
9
1000

1
2
4
5
7
8
10
11
14
1666

(Nguồn: CF 1560A có mở rộng thêm giới hạn)