Trong một buổi tiệc có \(n\) người tham gia trò chơi, người thứ \(i\) sẽ nhận được một tấm thẻ, trên đó ghi một số nguyên có giá trị \(a_i\) \((1 \le a_i \le 10^9)\).
Kết thúc buổi tiệc, người may mắn sẽ được nhận quà. Người thứ \(i\) được gọi là người may mắn nếu số lượng người có cùng giá trị \(a_i\) ghi trên thẻ là một số nguyên tố.

Yêu cầu: với mỗi vị trí \(i\), hãy cho biết người thứ \(i\) có phải là người may mắn hay không.
Nếu phải ghi ra 1, ngược lại ghi ra 0.

Dữ liệu vào

• Dòng 1: ghi số nguyên dương \(n\) (\(n \le 10^6\)).
• Dòng 2: ghi \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (các số được ghi cách nhau một dấu cách).

Dữ liệu ra

Gồm \(n\) dòng; dòng thứ \(i\) ghi 1 hoặc 0 tương ứng theo yêu cầu.

Ví dụ

7
5 4 4 3 3 3 3

0
1
1
0
0
0
0

Phân nhóm