北街梦寻 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