An gọi một số nguyên dương ~N~ là số gần chính phương khi tổng các chữ số của ~N~ là một số chính phương.

Bình vừa cầm thấy thú vị quá mới thổ với cách định nghĩa số gần chính phương của An nên Bình đã đưa ra một vài số nguyên dương để hỏi người An cho biết mỗi số mà Bình đưa ra có phải là số gần chính phương hay không?

Yêu cầu: bạn hãy viết một chương trình để với mỗi số mà Bình đưa ra, hãy in ra YES nếu đó là số gần chính phương hoặc NO nếu không phải.

Input

Vào từ file văn bản GANCP.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương ~T (2 \leq T \leq 10^4)~ là số tượng số mà Bình đưa ra

• ~T~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~A_i~ mà Bình đưa ra

Output

Ghi ra file văn bản GANCP.OUT gồm ~T~ dòng, dòng thứ ~i~ ghi YES nếu số ~A_i~ tương ứng trong file dữ liệu vào là số gần chính phương, ngược lại thì ghi NO.

Scoring

• Subtask ~1~ ~(40\%)~ tests tương ứng 40% số điểm có các số ~A_i \leq 10^4~.

• Subtask ~2~ ~(20\%)~ tests tương ứng 40% số điểm có các số ~A_i \leq 10^9~.

• Subtask ~3~ ~(20\%)~ tests tương ứng 40% số điểm có các số ~A_i \leq 10^{18}~.

• Subtask ~4~ ~(20\%)~ tests tương ứng 40% số điểm có các số ~A_i \leq 10^{40}~.

Example input 1

3
13
316
306

Example output 1

YES
NO
YES