2712: 最大公约数

小菜的妹妹小诗就要读小学了！正所谓计算机要从娃娃抓起，小菜决定在幼儿园最后一段轻松的时间里教妹妹编程。

小菜刚教完gcd即最大公约数以后，一知半解的妹妹写了如下一段代码：

sum:=0;

for i:=1 to n-1 do

for j:=i+1 to n do sum:=sum+gcd(i,j)

显然这个程序的效率是很低的，小明打算写一个更强的程序，在求出sum的同时比妹妹跑的更快。

第一行一个整数t，即表示有t组数据

接下来t行，每行一个整数n

t行，每行一个整数，表示n所对应的sum值

2
10
100

67
13015