Cho mảng số nguyên dương A gồm N phần tử.

Yêu cầu: Với mỗi phần tử, hãy kiểm tra xem nó có đúng 3 ước dương hay không. Nếu có in YES, ngược lại in NO.

Input

• Dòng đầu tiên gồm số nguyên dương N.
• Dòng thứ hai gồm N phần tử của mảng A.

Output

• Gồm N dòng, dòng thứ i là kết quả cho phần tử thứ i.

Scoring

• Subtask 1 (40%): 1 ≤ N ≤ 103, 1 ≤ Ai ≤ 103.
• Subtask 2 (30%): 1 ≤ N ≤ 103, 1 ≤ Ai ≤ 106.
• Subtask 3 (30%): 1 ≤ N ≤ 106, 1 ≤ Ai ≤ 1012.

Example

3
3 4 5

NO
YES
NO