#353. 军费

"这是军费，不能省！ I will give you Al~~~~~lof my money, Ocean Cat!" ——一只大哈鱼。
大哈鱼的作战计划需要大量的军费。他已经将他一个月的生活费捐献出去了，但还是远远不够，他开通了众筹通道。同为罗德岛的刀客塔，听了大哈鱼的作战计划，你很感动，也打算将自己的生活费捐献出去。
由于众筹通道是万恶的资本家设立的，资本家设定了一些规则。首先捐献的钱必须是大于等于 $2$ 的整数(否则手续费等于捐献的金额)，其次从这里通过的钱需要扣一部分手续费，手续费的数量为捐献的钱的最大因子（不含本身）。
你想尽可能让资本家少收取手续费，于是决定分批捐献。现在你打算捐 $N$ 元钱，请你安排一个合理的捐献方案，使得大哈鱼收到最多的钱。

多组测试数据。
第一行一个整数 $T (1 \leq T \leq 5000)$ ，表示数据数量。
接下来 $T$ 行，每行一个整数 $N(1 \leq N \leq 10^9)$，表示所捐的钱的数量。

$T$ 行，每行一个整数，表示大哈鱼最多收到的钱的数量。

样例输入

3
3
5
8

样例输出

2
4
6

样例说明

第一组和第二组直接捐献即可。
第三组分两次捐献，第一次捐 $3$ 元，扣去 $1$ 元，第二次捐 $5$ 元，扣 $1$ 元，总共扣 $2$ 元，大哈鱼拿到 $6$ 元。