A 除数减法

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

1、如果 n=0 ，结束算法；

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

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

输入

一行一个整数 t 表示测试的数量（1 <= t <= 10000）。 后面 t 行，每行一个整数 n（2 <= n <= 10^9）。

输出

输出一个整数——该算法进行循环操作的次数。

输入样例 2 5 4

输出样例 1 2