Description
小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，12=2*2*3 12的质因子有2，3 ，恰好为两种不同的质因子，因此12是幸运数字，而30=2*3*5，30的质因子有2，3，5，不符合要求，不为幸运数字。
小杨现在有n个正整数，他想知道每个正整数是否是他的幸运数字。
Input
第一行包含一个正整数n，代表正整数个数。
之后n行，每行一个正整数。
Output
输出n行，对于每个正整数，如果是幸运数字，输出1，否则输出0。
HINT
|
子任务编号
|
数据点占比
|
n
|
正整数值域
|
|
1
|
40%
|
<=100
|
<=105
|
|
2
|
60%
|
<=104
|
<=106
|
对于全部数据，保证有1<=n<=10
4，每个正整数a
i满足2<=a
i<=10
6。