背景

67讨厌数论，但是🏀杯国赛前一天晚上无事可做，67和同行的朋友决定VP一场牛客周赛......

描述

给定一个只包含一个整数 $n$ 的可重集 $\{n\}$。

操作：若存在正整数 $y, z$ 满足 $x = y + z$ 且 $\gcd(y, z) > 1$，则从集合中删除 $x$，加入 $y$ 和 $z$。

可以重复操作任意多次，问最后集合中最多能有多少个元素。

注：$\gcd(a, b)$ 表示 $a$ 和 $b$ 的最大公约数（Greatest Common Divisor），即能同时整除 $a$ 和 $b$ 的最大正整数。

输入格式

第一行一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例数量。

接下来 $T$ 行，每行一个整数 $n$ ($1 \le n \le 10^9$)。

输出格式

对于每个测试用例，输出一行一个整数，表示最终集合中元素的最大可能数量。

样例

3
1
4
6

1
2
3

限制

对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 10^9$。