4804 - 欧拉心算

给出一个数字N,求出\sum\limits_{i=1}^n\sum\limits_{j=1}^n\phi(\gcd(i,j))

第一行为一个正整数T，表示数据组数。

接下来T行为询问，每行包含一个正整数N。

T<=5000,N<=10^7

按读入顺序输出答案。