背景

经典的素数检测问题

题目描述

给你N个正整数，请依次判断每个数字是否为素数，若为素数，请输出1，不为素数则输出0.

Input

输入一共有两行，第一行有一个正整数N, 第二行有N个正整数，为需要判断的数据

Output

N 个数据，分别对应每个数据是否为素数

Samples

5
3 7 23 4 2

1 1 1 0 1

Limitation

1s, 1024KiB for each test case.

对于100%的数据，有 1<=N<=10000

给出的数据将不包含1