Số nguyên dương ~N~ được gọi là số đẹp nếu tích các số từ ~1~ đến ~N~ chia hết cho tổng các số từ ~1~ đến ~N~.

Yêu cầu

Với mỗi truy vấn, kiểm tra ~N~ có phải là số đẹp hay không.

Input

Dòng đầu chứa số nguyên dương ~T~ ~(1 \le T \le 10)~.

~T~ dòng tiếp theo, mỗi dòng chứa số nguyên dương ~N~ ~(1 \le N \le 10^9)~.

Output

In ra ~T~ dòng. Nếu ~N~ là số đẹp thì in YES, ngược lại in NO.

Subtask

• Có 40% số điểm có ~N \le 15~.
• Có 30% số điểm có ~15 < N \le 10^6~.
• Có 30% số điểm còn lại không có ràng buộc bổ sung.

Ví dụ

2
6
7

NO
YES