P10720 [GESP202406 Level 5] Xiao Yang's Lucky Number

Corresponding multiple-choice and true/false problems: .

Xiao Yang believes that his lucky number should have exactly two distinct prime factors. For example, $12 = 2 \times 2 \times 3$ has prime factors $2, 3$, which are exactly two distinct prime factors, so $12$ is a lucky number. However, $30 = 2 \times 3 \times 5$ has prime factors $2, 3, 5$, which does not meet the requirement, so it is not a lucky number. Xiao Yang now has $n$ positive integers, and he wants to know whether each positive integer is his lucky number.

The first line contains a positive integer $n$, representing the number of positive integers. The next $n$ lines each contain one positive integer.

Output $n$ lines. For each positive integer, if it is a lucky number, output $1$; otherwise output $0$.

### Sample Explanation The prime factors of $7$ are $7$, which is only one kind. The prime factors of $12$ are $2, 3$, which is exactly two kinds. The prime factors of $30$ are $2, 3, 5$, which is three kinds. ### Constraints Subtask ID | Percentage | $n$ | Range of positive integers :-: | :-: | :-: | :-: $1$ | $40\%$ | $\leq 100$ | $\leq 10^5$ $2$ | $60\%$ | $\leq 10^4$ | $\leq 10^6$ For all testdata, it is guaranteed that $1 \leq n \leq 10^4$, and each positive integer $a_i$ satisfies $2 \leq a_i \leq 10^6$. Translated by ChatGPT 5