Tito học toán siêu cao cấp cho học sinh lớp 5 có bài toán chuyển đổi một số từ cơ số 10 sang cơ số 3 bằng cách biểu diễn số đó thành tổng các lũy thừa của 3 với các hệ số 0,1,2 ta được số đó ở cơ số 3

Ví dụ

$n=101$ ta có biểu diễn $101=1\ast 3^4+0\ast 3^3+2\ast 3^2+0\ast 3^1+2\ast 3^0$ nên sang cơ số 3 thành 10202

Tito làm mãi mà không được bạn hãy giúp Tito nhé

Input

Dòng đầu gồm số bộ test $t1\le t\le 100$

Tiếp theo $t$ dòng mỗi dòng chứa một số nguyên dương $n$ nhỏ hơn 10^9

Output

Gồm $t$ dòng mỗi dòng là một biểu diễn tương ứng của $n$ sang cơ số 3

Ví dụ

Input

5
354
551
536
561
459

Output

111010
202102
201212
202210
122000