回复 @Mike is Fool :
可以证明phi（T）= sigma ( d | T )u( T / d )* d

线性筛，隐式莫反（构造f函数的时候用的），分块，O(n)预处理，O(sqrt(n))查询
其中定义f(x)=(d|x)d*miu[x/d]，不难证明f函数的积性，之后有假设1<=i,j<=n，ans=(1<=x<=n)(n/x)*(n/x)*f(x)（莫反的枚举变量交换一下），询问分块就好了。
不难证明，F(x)=(d|x)f(x)=x（莫比乌斯反演公式可证）
所以也可以杜教筛求f函数的前缀和，每次询问O(n^(2/3))，预处理O(n^(2/3))。
这真是智障，我用莫比乌斯函数求出来了欧拉函数- -

单次O(输入的n)查询还是过了...

欧拉函数前缀和
O(n)预处理 + O(sqrt(n))单次询问

论大小号同时提交的后果......
然后...O(nlnn)的垃圾筛慢成翔啊......A不A全看评测机心情......

O（n）做法

模板就是硬

回复 @<大神养成>溪哥 :
。。。。。。ORZ

样例更新了？好评！

谁出的这道题。。。。。。
调了一个小时，发现样例错了。。。。。。
出题人，我要跟你拼了！

回复 @weizj :
高大上的解法……
由于T小，因此这道题在线回答更好，这个想法不错

回复 @cstdio :
好吧。。我打错了。。应该就是预处理复杂接近NLOGN的。。

回复 @cstdio :
我指的是预处理的复杂度是N*LOGN，每次询问时枚举因数再分块优化可以做到每次询问的复杂度为N^0.5（这里需要用欧拉函数预处理1到N范围内互质数对的个数），总复杂度为N*LOGN+T*N^0.5.

回复 @weizj :
求解，怎么做到的……筛法求欧拉函数不是O(nlogn)吗？

回复 @weizj :
好神奇的优化

筛法求欧拉函数，最后求解时再分块优化。。类似HAOI2011问题B，可以做到O(N^0.5*t).

正确率被我刷低了