Problem Description

Define $f(x)$ as the number of prime factors of $x$ after prime factorization, counting multiplicities. For example, $f(6)=2$ and $f(12)=3$.

Specifically, let $x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where $p_1,p_2,\ldots,p_k$ are pairwise distinct primes. Then $f(x)=a_1+a_2+\cdots + a_k$.

Given a number $n$, determine whether there exists an integer $m$ with $1<m<n$ such that $f(m)>f(n)$.

Input Format

The first line contains an integer $T$, which represents the number of test cases.

The next $T$ lines each contain a positive integer $n$.

Output Format

Output $T$ lines. For the $i$-th test case, if the given $n$ has some $m$ satisfying $1<m<n$ and $f(m)>f(n)$, output a single number $1$ on one line; otherwise output a single number $0$ on one line.

6
2
3
4
5
12
514

0
0
0
1
0
1

Hint

Sample Explanation #1

$f(2)=1$, and there is no $1<x<2$ with $f(x)>1$.

$f(3)=1$, and there is no $1<x<3$ with $f(x)>1$.

$f(4)=2$, and there is no $1<x<4$ with $f(x)>2$.

$f(5)=1$, and $f(4)=2$ exists.

$f(12)=3$, and there is no $1<x<12$ with $f(x)>3$.

$f(514)=2$, and $f(114)=3$ exists.

Constraints

For all testdata, $1\leq T\leq 10^4$ and $2\leq n\leq 10^{18}$. The detailed constraints are as follows:

• Subtask #1 (25 pts): $T,n\le 10$.
• Subtask #2 (35 pts): $n\le 10^5$.
• Subtask #3 (15 pts): $T\le 10$, and $n$ is generated uniformly at random in $[2,10^{18}]$.
• Subtask #4 (25 pts): No additional constraints.

Translated by ChatGPT 5