HZNUOJ

北街梦寻

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:107     AC:17     Score:99.16

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

input
3 1 2 3
output
1 3 7

Hint


Author

HU, Haoquan