小杨认为他的幸运数字应该恰好有两种不同的质因子，例如， $ 12=2×2×3 $ 的质因子有 $ 2,3 $ ，恰好为两种不同的质因子，因此 $ 12 $ 是幸运数字，而 $ 30=2×3×5 $ 的质因子有 $ 2,3,5 $ ，不符合要求，不为幸运数字。
小杨现在有 $ n $ 个正整数，他想知道每个正整数是否是他的幸运数字。
输入格式
第一行包含一个正整数 $ n $ ，代表正整数个数。
之后 $ n $ 行，每行一个正整数。
输出格式
输出 $ n $ 行，对于每个正整数，如果是幸运数字，输出 $ 1 $ ，否则输出 $ 0 $ 。
样例输入1
3
7
12
30
样例输出1
0
1
0
提示
样例解释
$ 7 $ 的质因子有 $ 7 $ ，只有一种。
$ 12 $ 的质因子有 $ 2，3 $ ，恰好有两种。
$ 30 $ 的质因子有 $ 2，3，5， $ 有三种。
数据范围
| 子任务编号 | 数据点占比 | $ n $ | 正整数值域 |
|---|---|---|---|
| $ 1 $ | $ 40% $ | $ ≤100 $ | $ ≤10^5 $ |
| $ 2 $ | $ 60% $ | $ ≤10^4 $ | $ ≤10^6 $ |
对于全部数据，保证有 $ 1≤n≤10^4 $ ，每个正整数 满足 $ 2≤a_i≤10^6 $ 。