有些人如果不把实际任务隐藏在复杂且有些多余的故事中，就不会对解决问题感到满意。如果你是这类人，那么这道题正适合你。

作为当地一家糖果厂的环境专家，你的生活再甜蜜不过了，无论是比喻意义上还是字面意义上。而且你的生活注定会变得更加甜蜜，因为如果你能将公司的塑料足迹减半，你就会获得晋升——当然，你正打算这样做。

目前，工厂每天使用大量的塑料包装——它生产 $n$ 种糖果，编号从 $1$ 到 $n$，并且每种糖果都用一个单独的袋子包装。你的绝妙主意是简单地开始每个袋子包装两种糖果，从而将使用的袋子数量减半！

不过别高兴得太早——事情没那么简单。第 $i$ 种糖果的产量总是 $i$ 个，现在被装进一个袋子里。如果两种糖果（比如第 $i$ 种和第 $j$ 种）被装进同一个袋子里，你需要确保共享袋子里的糖果可以被一群朋友公平且均匀地分配。形式化地说，你希望 $i$ 和 $j$ 有一个大于 $1$ 的公约数。

你可以将一些糖果配对装在一个袋子里，并将剩余的糖果放在各自的袋子里。你最少需要多少个袋子？

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 5$)。接下来是各测试用例的描述。 每个测试用例只有一行，包含一个数字 $n$ ($2 \le n \le 10^{11}$)，即工厂生产的糖果种类数。

输出格式

对于每个测试用例，输出一行，包含所需的最少袋子数量。

样例

输入格式 1

2
4
9

输出格式 1

3
6