该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在遥远的数理王国中，流传着“素源封印”的古老仪式。

王国中散落着 $n$ 块蕴含不同频率的符晶，编号依次为 $1,2,\dots,n$。据传，若将符晶随意堆置，频率共振会引发灾难；唯有将它们分门别类，按照“共振和谐”的原则排列，方能将其能量安稳封印。

• 对任意两块符晶 $i$ 与 $j$，定义它们的共振强度为：$$\gcd(i,j)$$
• 若两块符晶的共振强度大于 $1$，则它们会产生不稳定谐振；只有当 $\gcd(i,j) = 1$ 时，这对符晶才能在同一阵列中和谐共存。

题目描述

国王下旨：

“诸贤将此 $n$ 块符晶，按照安全共存之道，分置于若干封印阵列中，以镇压其潜在能量。务必使得每个阵列内的任意两块符晶均满足 $\gcd(i,j)=1$。问：最少需要多少个封印阵列，方可完成此殊胜之举？”

输入格式

第一行一个整数 $Q$，代表国王有 $Q$ 次询问。

接下来 $Q$ 行，每行一个正整数 $n$，表示符晶数量。

输出格式

$Q$ 行，每行一个整数，表示至少需要的封印阵列数。

样例输入输出

样例 1

输入

2
2
7

输出

1
3

数据范围与提示

• $1 \le Q \le 10^6$
• $1 \le n \le 10^{18}$