题目描述

定义 $f(x)$ 表示 $x$ 分解质因数后得到的质数个数，例如 f(6)=2,f(12)=3。 具体的，令$x={{p_1}^{a_1}}{{p_2}^{a_2}}……{{p_k}^{a_k}}$，其中${p_1}，{p_2}，……{p_k}$是两两不同的质数，则$f(x)={a_1}+{a_2}+……+{a_k}$。 给定一个数$n$,判断是否存在$1<m<n$,满足$f(m)>f(n)$。

输入格式

第一行一个整数 $t$，表示数据组数。

随后 $t$ 行，每行一个正整数 $n$。

对于所有数据，满足 $1\leqslant t\leqslant {10^4}$，$1 \leqslant n \leqslant 2\times 10^9$。

输出格式

输出$t$ 行，若对于第$i$组数据给定的$n$存在 $1<m<n,f(m)>f(n)$输出一行一个数 1，否则输出一行一个数 0。

样例

6
2
3
4
5
12
514

0
0
0
1
0
1

限制

1s, 1024KiB for each test case.