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\le {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\ge 0)$.

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

Constraint