Có ~n~ người tham gia trò chơi, người thứ ~i~ nhận thẻ ghi số nguyên ~a_i~. Người thứ ~i~ là người may mắn nếu số lượng người có cùng giá trị ~a_i~ là một số nguyên tố.

Yêu cầu

Với mỗi vị trí, in ~1~ nếu người đó may mắn, ngược lại in ~0~.

Input

Dòng đầu chứa ~n~ ~(1 \le n \le 10^6)~.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~.

Output

In ~n~ dòng, dòng thứ ~i~ là kết quả của người thứ ~i~.

Subtask

• Có 50% số test có ~n \le 10^3~, ~a_i \le 10^6~.
• Có 50% số test còn lại có ~n \le 10^6~, ~a_i \le 10^9~.

Ví dụ

7
5 4 4 3 3 3 3

0
1
1
0
0
0
0