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~. Ví dụ 3, 7, 8 là những số đẹp.

Yêu cầu: Kiểm tra số nguyên ~N~ có phải là số đẹp hay không?

Input

• Dòng đầu ghi số nguyên dương ~T~ (~1 \le T \le 10~) là số lượng test cần kiểm tra.
• ~T~ dòng tiếp theo, mỗi dòng ghi một số nguyên dương ~N~ (~1 \le N \le 10^9~).

Output

Ghi ra ~T~ dòng, mỗi dòng là kết quả tương ứng các lượt kiểm tra, nếu ~N~ là số đẹp thì ghi YES, ngược lại ghi NO.

Sample Input 1

2
6
7

Sample Output 1

NO
YES

Ràng buộc

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