请教大家没算法解出此题增加效率

定义如果<x0,y0>和<x1,y1>满足x0-x1=y0-y1，则称这两个为等差对。
mm的问题是，问在<x,y>（0<=x,y<=n）<0,0>,<0,1>…<1,0>,<1,1>…<2,0>,
<2,1>…<n,0>…<n,1>…这(n+1)^2个有序对中存在多少个等差对？
第一行输入一个整数T(T<=1000)，表示case数。
下面T行有T个case，每个case只有一个整数n（1<=n<=10^9），表示0<=x,y<=n
每个case输出一行,表示等差对的数量，这个结果可能很大，只需最后结果%20111111即可。
我的代码暴力超时
      while(T--)
    {
        s=0;
        scanf("%lld",&n);
        s+=((n%20111111)*(n+1)%20111111)%20111111/2;
        for( i=n;i>1;i--)
        {
            s+=(i%20111111)*((i-1)%20111111)%20111111;
        }
        s%=20111111;
        printf("%lld\n",s);
    }