Chữ số "rỗng" là chữ số có phần rỗng ở giữa. Các chữ số "rỗng" là \(0,\) \(4,\) \(6,\) \(8,\) \(9\).
Số "khác rỗng" là số mà không có chữ số "rỗng". Các số "khác rỗng" đầu tiên là \(1,\) \(2,\) \(3,\) \(5,\) \(7,\) ...

Input

• Dòng đầu tiên nhập vào một số nguyên dương \(t\) (\(t \le 10^4\)) - số lượng truy vấn.
• \(t\) dòng tiếp theo, mỗi dòng nhập vào một số nguyên dương \(n\) (\(n \le 10^{12}\)).

Output

• Với mỗi truy vấn, hãy in ra số "khác rỗng" thứ \(n\).
• Dữ liệu đảm bảo kết quả in ra luôn bé hơn \(2^{63}\).

Example

5
2 
4
16 
17
23

2
5
31
32
53

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(t \le 10\), \(n \le 10^4\).
• Subtask \(2\) (\(20\%\) số điểm): \(t \le 10^4\), \(n \le 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): \(t \le 10^4\), \(n \le 10^{12}\).