Số nguyên thủy ~N~ là số có thể được biểu diễn dưới dạng tổng của các lũy thừa của ~3~ như sau: ~N=3^{k_{1}}+3^{k_{2}}+\cdot\cdot\cdot+3^{k_{m-1}}+3^{k_{m}}~

Trong đó: ~0 \le k_{1} < k_{2} < \cdot\cdot\cdot < k_{m}~

Trường hợp đặc biệt: ~N=1~ được xem là số nguyên thủy đầu tiên vì ~1=3^{0}~. Ví dụ: ~31=3^{0}+3^{1}+3^{3}~.

Yêu cầu: Cho số nguyên dương ~N~, hãy xác định xem ~N~ có phải là số nguyên thủy theo định nghĩa trên hay không?

Input

• Dòng đầu ghi số nguyên ~T~ là số lượng test ~(1 \le T \le 100)~.

• Dòng thứ ~i~ trong ~T~ dòng tiếp theo, ghi số nguyên dương ~N~ ~(N \le 10^{18})~.

Output

Tương ứng mỗi test ghi kết quả trên một dòng:

• True: Nếu ~N~ là số nguyên thủy.

• False: Trong trường hợp ngược lại.

Scoring

Sample Input 1

7
1
8
13
20
18
31
199

Sample Output 1

True
False
True
False
False
True
False