Background

Corresponding multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1153.

Problem Description

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.

Input Format

The first line contains a positive integer $n$, representing the number of positive integers.

The next $n$ lines each contain one positive integer.

Output Format

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

3
7
12
30

0
1
0

Hint

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

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