Vì học toán rất ngu nên Tèo chỉ biết ~3~ số đầu trong dãy lũy thừa lủa ~3~, đó là ~1~, ~3~, ~9~. Anh đang thắc mắc rằng liệu có số nào lớn hơn trong dãy hay không, vì vậy Tèo liền nảy ra một ý tưởng càng ngu hơn bằng cách viết lên bảng một số ~N~ rất lớn, và tự hỏi xem số này có phải lũy thừa của ~3~ hay không, hãy giúp Tèo thực hiện ý tưởng của anh!

Input

• Dòng đầu tiên nhập vào ~T~ là số lượng truy vấn.

• ~T~ dòng sau, mỗi dòng nhập vào một số ~N~ ~(N \leq 10^{1000000})~.

Output

• Với mỗi truy vấn, in ra "Yes" hoặc "No" (không ngoặc kép) nếu ~N~ là lũy thừa của ~3~ và ngược lại.

Sample Input

2
9
2

Sample Output

Yes
No

Note

Lũy thừa của ~3~ là số có dạng ~3^x~ ~(x \geq 0)~.

VD: ~3^0 = 1~, ~3^1 = 3~, ~3^2 = 9~.

Constraint