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.

INPUT

• 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).

OUTPUT

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

SAMPLE INPUT 1

7
5 4 4 3 3 3 3

SAMPLE OUTPUT 2

0
1
1
0
0
0
0

• Người thứ 1: giá trị 5 xuất hiện 1 lần → 1 không phải số nguyên tố → in 0.
• Người thứ 2 và 3: giá trị 4 xuất hiện 2 lần → 2 là số nguyên tố → in 1 cho cả hai vị trí.
• Người thứ 4,5,6,7: giá trị 3 xuất hiện 4 lần → 4 không phải số nguyên tố → in 0 cho cả bốn vị trí.

SUBTASKS