Hôm nay An được thầy giáo dạy về chủ đề ước và bội của các số nguyên. Thầy giáo đố An đếm được có bao nhiêu số có đúng 3 ước dương trong n số nguyên không âm thầy đã cho và treo thưởng 50k nếu An làm được. An rất phân khích, nhưng mà câu nghi mãi vẫn chưa ra cách làm. Các bạn hãy giúp An lấy giải 50k của thầy giáo nhé.

Input

• Dòng 1 chứa số nguyên dương \(n\) (\(0 \leq n \leq 10^6\)).
• Dòng 2 chứa \(n\) số nguyên dương \(a_i\) (\(0 < a_i \leq 10^{12}\)).

Output

• Ghi vào tệp \(n\) dòng, dòng thứ \(i\) ghi YES nếu \(a_i\) có đúng 3 ước dương, còn ngược lại thì ghi NO.

Example

10
1 2 3 4 5 6 7 8 9 25

NO
NO
NO
YES
NO
NO
NO
NO
YES
YES