Một số được gọi là số tree_num khi nó được là tổng của các lũy thừa cơ số ~3~ với số mũ không âm tăng dần.

Ví dụ ~30=3^1+3^3~; ~325=3^0+3^4+3^5~ là những số tree_num.

Yêu cầu :Tìm số tree_num thứ ~n~.

Input

Dòng đầu chứa số nguyên dương ~t~ là số test ~(t \leq 30000)~.

~t~ dòng sau, mỗi dòng chứa số nguyên dương ~n~ ~(0 < n < 2^{64})~.

Output

~t~ dòng mỗi dòng chứa số tree_num thứ ~n~.

Sample Input

5
1
2
7
3
6

Sample Output

1
3
13
4
12