Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:512 MB

#149. 质因数

统计

题目描述

定义 $f(x)$ 表示 $x$ 分解质因数后得到的质数个数,例如 $f(6)=2,f(12)=3$。

具体地,令 $x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$,其中 $p_1,p_2,\ldots,p_k$ 是两两不同的质数,则 $f(x)=a_1+a_2+\cdots + a_k$。

给定一个数 $n$,判断是否存在 $1 < m < n$,满足 $f(m)>f(n)$。

输入格式

第一行一个整数 $T$,表示数据组数。

接下来 $T$ 行,每行一个正整数 $n$。

输出格式

输出 $T$ 行,若对于第 $i$ 组数据给定的 $n$ 存在 $2\le m\le n-1,f(m)>f(n)$ 输出一行一个数 $1$,否则输出一行一个数 $0$。

样例

样例输入

6
2
3
4
5
12
514

样例输出

0
0
0
1
0
1

样例解释

$f(2)=1$,不存在 $2\le x<2,f(x)>1$。

$f(3)=1$,不存在 $2\le x<3,f(x)>1$。

$f(4)=2$,不存在 $2\le x<4,f(x)>2$。

$f(5)=1$,存在 $f(4)=2$。

$f(12)=3$,不存在 $2\le x<12,f(x)>3$。

$f(514)=2$,存在 $f(114)=3$。

数据范围

对于所有数据,满足 $1\leq T\leq 10^4$,$2\leq n\leq 10^{18}$。详细数据范围如下:

  • Subtask #1 (25 pts): $T,n\le 10$。
  • Subtask #2 (35 pts): $n\le 10^5$。
  • Subtask #3 (15 pts): $T\le 10$,$n$ 在 $[2,10^{18}]$ 内均匀随机生成。
  • Subtask #4 (25 pts):没有任何附加限制。