#1826. 质因数

质因数

题目描述

定义f(x)f(x) 表示 xx 分解质因数后得到的质数个数,例如 f(6)=2,f(12)=3f(6)=2,f(12)=3

具体的,令 x=p1a1p2a2pkakx=px=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}x=p ,其中,p1,p2pkp_1,p_2\cdots p_k是两两不同的质数,则 f(x)=a1+a2+akf(x)=a_1+a_2\cdots +a_k 给定一个数 nn,判断是否存在 1<m<n1<m<n,满足 f(m)>f(n)f(m)>f(n)

输入格式

第一行一个整数 TT,表示数据组数。

接下来 TT 行,每行一个正整数 nn

输出格式

输出 TT 行,若对于第 ii 组数据给定的 nn 存在 1<m<n,f(m)>f(n)1<m<n,f(m)>f(n) 输出一行一个数 11,否则输出一行一个数 00

样例

6
2
3
4
5
12
514
0
0
0
1
0
1