Định nghĩa 𝓢𝓸̂́ 𝓼𝓪̀𝓷𝓰 𝓵𝓸̣̂𝓬 \(:\)

• Số đó là \(1\) số chính phương \(.\)
• Sô đó có \(1\) ước nguyên tố trừ 1 và chính nó \(.\)
  VD :
  \(25\) là 𝓢𝓸̂́ 𝓼𝓪̀𝓷𝓰 𝓵𝓸̣̂𝓬 \(.\)
  vì \(25\) là 1 số số chính phương \(.\)
  và \(25\) có tất cả ước là \(1, 5, 25 .\)
  trừ \(1\) và chính nó là \(25\) thì \(5\) là \(1\) số nguyên tố \(.\)

Yêu cầu

• cho \(Q\) truy vấn \(.\) và số nguyên dương \(N .\)
• Hãy kiểm tra xem \(N\) có phải là 𝓢𝓸̂́ 𝓼𝓪̀𝓷𝓰 𝓵𝓸̣̂𝓬 hay không \(.\)
  nếu là 𝓢𝓸̂́ 𝓼𝓪̀𝓷𝓰 𝓵𝓸̣̂𝓬 thì in ra 1, ngược lại thì in ra 0 \(.\)

Input

• Số nguyên dương \(Q\) \((1 \le Q \le 10^{6}) .\)
• Với mỗi truy vấn nhập số nguyên dương \(N\) \((1 \le N \le 10^{12}) .\)

Output

• Làm theo yêu cầu của đề lưu ý không cách dòng hay xuống dòng để để cách ta viết liền các kết quả 1 và 0 \(.\)

Example

5
1
4 
25 
122 
43

01100