给定一个整数 n ，按照如下算法进行操作：

1 、如果 n=0,结束算法;

2 、找到 n 的最小质因子 d ；

3、 n-=d 并回到操作 1 。

一行一个整数 t 表示测试的数量。

后面 t 行，每行一个整数 n。

输出一个整数——该算法进行循环操作的次数（对于每个数字n）。

50%数据，1 \leq T \leq 100，1 \leq n \leq 10^3。

100%数据，1 \leq T \leq 10000，1 \leq n \leq 10^9。