当前没有测试数据。

小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，12 = 2 × 2 × 3 12=2\times 2\times 312=2×2×3 的质因子有 2 , 3 2,32,3，恰好为两种不同的质因子，因此 12 1212 是幸运数字，而 30 = 2 × 3 × 5 30=2\times3\times530=2×3×5 的质因子有 2 , 3 , 5 2,3,52,3,5，不符合要求，不为幸运数字。

小杨现在有 n nn 个正整数，他想知道每个正整数是否是他的幸运数字。

输入格式 第一行包含一个正整数 n nn，代表正整数个数。

之后 n nn 行，每行一个正整数。

输出格式 输出 n nn 行，对于每个正整数，如果是幸运数字，输出 1 11，否则输出 0 00。

输入输出样例 #1 输入 #1 3 7 12 30 1 2 3 4 输出 #1 0 1 0 1 2 3 说明/提示 样例解释 7 77 的质因子有 7 77，只有一种。

12 1212 的质因子有 2 , 3 2,32,3，恰好有两种。

30 3030 的质因子有 2 , 3 , 5 2,3,52,3,5，有三种。

数据范围 子任务编号 数据点占比 n nn 正整数值域 1 11 40 % 40%40% ≤ 100 \leq 100≤100 ≤ 1 0 5 \leq 10^5≤10 5

2 22 60 % 60%60% ≤ 1 0 4 \leq 10^4≤10 4 ≤ 1 0 6 \leq 10^6≤10 6

对于全部数据，保证有 1 ≤ n ≤ 1 0 4 1\leq n\leq 10^41≤n≤10 4 ，每个正整数 a i a_ia i ​ 满足 2 ≤ a i ≤ 1 0 6 2\leq a_i\leq 10^62≤a i ​ ≤10 6 。 ————————————————