北街梦寻 2722
Description
北山街东起环城西路、西至灵隐路、南傍里西湖、北靠宝石山，它是以秀美山水为载体，以历史文化为灵魂，以近代建筑为骨架，集自然与人文景观为一体的历史、文化街区。 它历史沉淀深厚：浙赣铁路局旧址，记载着抗日战争的风云；首届西湖博览会工业馆，寄托了前辈富民强国的凌云壮志；秋水山庄，演绎过壮烈凄美的故事；穗庐留下了巴金老人的珍贵“手迹”；菩提精舍，静逸别墅、抱青别墅等。一条长仅千余米的北山街，风光绮丽、蜿蜒漫长，这里有许多历史建筑遗迹，保留着古朴的原貌，串起了许多萦绕人心的魂梦。
现在北街新建了一个灯墙，灯墙的管理维护工作交给了Donald。灯墙上的$n^2$个灯泡排列成了一个$n*n$的矩阵。但是这个灯墙的打开方式非常奇怪，在每一个坐标各有一个按钮。当你按下坐标（$x，y$）的按钮时，所有坐标为（$k*x，k*y$）的所有灯泡都会点亮（$1 \leq k$）。举个栗子，假如你按下了位置为（$2，3$）的按钮时，（$4，6$），（$6，9$）……（$2*k，3*k$）位置的灯泡都会被点亮。初始所有灯泡都不亮。Donald想用最少次数的操作，使得所有灯泡点亮。但是Donald无法计算出答案，请你编一个程序帮助Donald计算对于给定的n，点亮所有灯泡的最小次数。每组样例的初始状态下，所有灯泡都不亮。
Input
第一行是一个整数t，表示一共有T组数据，$1 \leq t \leq 10000$。
接下来t行，每一行是一个整数n，表示n*n的灯泡矩阵，$1 \leq n \leq 5000000$。
Output
对于每一组数据，输出点亮所有$n*n$个灯泡的最小操作次数。
Samples
Hint