Bé Mạnh đang học lớp 1.

Các bạn khi làm contest này chắc cũng đã nghe qua trường tiểu học SFITKids, với những đứa trẻ cực kỳ vjp pro, và bài thi đầu vào có độ khó cực gắt.

Trong một tiết toán của thầy Kiên về bảng cửu chương, vì lí do nào đó Mạnh đã trốn tiết thầy Kiên hôm thầy ấy dạy bảng cửu chương của số 3, những buổi học sau đó vì cảm thấy không hiểu bài nên Mạnh cảm thấy rất ghét số 3 từ đó Mạnh cũng ghét luôn các số chia hết cho 3 hoặc các số có biểu diễn thập phân kết thúc là chữ số 3. Những số thỏa mãn cả 2 điều kiện đó Mạnh càng ghét nữa.

Thầy Kiên vì muốn chiều Mạnh nên đã yêu cầu Mạnh viết ra 1 dãy số nguyên dương bắt đầu từ 1 và không bao gồm những số mà Mạnh ghét để Mạnh không phải gặp số mình ghét nữa :3.

• Ví dụ: 10 phần tử đầu tiên của dãy số: 1,2,4,5,7,8,10,11,14,16,...

Vì dãy số trên rất dài, mọi người hãy giúp thầy Kiên tìm nhanh ra số thứ k ở trong dãy nhé.

Đầu vào

Dòng đầu chứa số nguyên \(T\) là số lượng bộ test. \((1 \le T \le 10^6)\)

\(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(k\). \((1 \le k \le 10^{6})\)

Đầu ra

\(T\) dòng, mỗi dòng là số thứ k mà bạn tìm được trong dãy nhé.

Ví dụ

Đầu vào

5
1
2
5
7
1000

Đầu ra

1
2
7
10
1666