TREENUM - Tree Num

Giới hạn
  • Thời gian: 0.289s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

 

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 ntest là số test(ntest<=30000)

Ntest dòng sau:mỗi dòng chứa số nguyên dương n (0 < n < 2^64)

Output

 

Ntest dòng mỗi dòng chứa số tree_num thứ n

 

Sample

Input:
5
1
2
7
3
6
Output:
1
3
13
4
12


  • Người up: vdmedragon
  • Nguồn bài: Lê Vãn Tấn Quyền