Problem C

Alice 和 Bob 又在玩游戏了！
这一次，他们发明了一个关于数列的游戏。
首先，他们在黑板上写下了1到N这N个数字。在游戏过程中，他们轮流从黑板上选择一个数字，然后把它和它的所有约数全部从黑板上擦去。

我们想知道的是，如果Alice和Bob想合力把所有数字都擦掉的话，最少需要执行多少次擦除的操作？

输入的第一行是测试数据的组数T(T<=10)。

每组测试数据仅包含一个整数N(1<=N<=10⁴)。

对于每组测试数据，输出最少需要的操作次数。

2
1
2

1
1

校第十六届大学生程序设计竞赛暨2016省赛集训队选拔赛