#G1053. [GESP202406 五级] 小杨的幸运数字

[GESP202406 五级] 小杨的幸运数字

[GESP202406 五级] 小杨的幸运数字

题目描述

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

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

输入格式

第一行包含一个正整数 nn,代表正整数个数。

之后 nn 行,每行一个正整数。

输出格式

输出 nn 行,对于每个正整数,如果是幸运数字,输出 1,否则输出 0。

样例 #1

样例输入 #1

3
7
12
30

样例输出 #1

0
1
0

样例解释

7 的质因子有 7,只有一种。

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

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

数据范围

子任务编号 数据点占比 nn 正整数值域
1 40% n≤100n ≤ 100 ≤105≤ 10^5
2 60% n≤104n ≤ 10^4 ≤106≤ 10^6
  • 对于全部数据,保证有 1≤n≤1041 ≤ n ≤ 10^4,每个正整数 aia_i 满足 2≤ai≤1062 ≤ a_i ≤ 10^6。

时间限制:1.0 s。内存限制:512.0 MB。