A.  A Simple Game

--------------------------------------------------------------------------------

Time Limit: 1.0 Seconds  Memory Limit: 65536K
Total Runs: 0  Accepted Runs: 0

--------------------------------------------------------------------------------


Alice likes to play games. One day she meets such a game. There are N * N switches arranged in an N * N array. Pressing a switch would change its state, from 'off' to 'on' or from 'on' to 'off'. In addition, if a switch at row r and column c is pressed, then all switches with coordinate (k * r, k * c) will change state, with integer k > 1. Initially all switches are 'off'.



For example, in the picture above, white buttons represent switches turned 'off' and colored ones represent switches turned 'on'. Initially all buttons are white. If the button at (2,2) is pressed, then buttons at (2,2), (4,4) will change state(represented with orange color). And if one presses the button (2,1), buttons at (2,1) and (4,2) will change from 'off' to 'on'(represented with gray color).

The goal of the game is to turn 'on' all the switches (i.e. when you finish the game, all the switches must be at the state of 'on') and the player must do that with as few presses as possible. Now Alice would like your help.


Input
The first line of input file is an integer T, the number of test cases. T lines follow, each contain an integer N, the dimension of the array in one game.

Output
Output consists of T lines. Each line contains an integer, the minimum number of presses for the corresponding test case.
Constraints
1 ≤ T ≤ 100, 1 ≤ N ≤ 10000
Sample Input
2
2
3

Sample Output
3
7

Sample Input/Output Clarification
For test case 1, press (1,1) (1,2) (2,1).
For test case 2, press (1,1) (1,2) (1,3) (2,1) (2,3) (3,1) (3,2).







怎么实现内存啊  不能用10000维的数组啊！！！

小于一百维的我弄出来了  但是大于一百维的有点困难  想用位操作  可是有点困难啊    昨天有人做出来了  不知道怎么做的？？

欧拉函数。。。

你定义2维数组是不行的，我也试过了，定义10000，元素就有100000000个，大小已经超过默认栈的大小了，如果想用，就把数组定义成全局，可以运行，但是内存使用和运行时间都超标

我觉得这个题目有递推关系

o 个人也这样认为  可是我用位操作还是内存不够  不知道怎么回事 
另外再问个问题  Multiple test files是什么意思啊  不要代码 还是用什么多媒体文件？ 解释一下 谢谢

I am not sure whether this is a problem of binary match!