Các bạn có 1 số nguyên dương ~N~ và bạn hãy tìm ra số đẹp nhỏ nhất mà lớn hơn hoặc bằng ~N~. Với số đẹp ở đây là số được tạo thành từ tổng các số lũy thừa của 3 khác nhau

Ví dụ:

• ~4~ là số đẹp vì ~ 4 = 3^1 + 3^0~
• ~30~ là số đẹp vì ~30 = 3^3 + 3^1 ~
• ~6~ không phải số đẹp vì ~ 6 = 3^1 + 3^1 ~(chứa 2 lần ~3^1~)
• ~20~ cũng không phải số đẹp vì ~20 = 3^2 + 3^2 + 3^0 + 3^0~

Input

• Dòng đầu tiên chứa số nguyên ~T~ ~(1 \le T \le 500)~
• ~T~ dòng tiếp theo mỗi dòng chứa số nguyên dương ~N~ ~(1 \le N \le 10000)~

Output

In kết quả là số thỏa mãn yêu cầu đề bài trên từng dòng tương ứng với từng test

Sample

Input #1

5
1
2
14
360
10000

Output #1

1
3
27
360
19683

Problem source: CLB Lập Trình PTIT