小歪的数字问题

题解思路

1. 题目要求计算所有满足 1 ≤ i < j ≤ n 的二元组 $(i,j)$ 对应的值
   $\frac{i+j}{\gcd(i,j)}$
   的总和，并对 $10^9+7$ 取模。

2. 注意到令 $d=gcd(i,j)$，令 $i=d \cdot a, j=d\cdot b$ 且 $\gcd(a,b)=1$（且 $a<b$），有

题目内容

对于给定的整数$n$，对于全部的二元组$(i,j)$满足$1≦i<j≦n$，计算$\frac{i+j}{gcd{i,j}}$之和。由于答案可能很大，请将答案对$(10^9+7)$取模后输出。

$gcd$，即最大公因数，指两个整数共有约数中最大的一个。例如，$12$和 $30$的公约数有$1,2,3,6$，其中最大的约数是$6$，因此$gcd(12,30) =6$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≦T≤10^5)$代表数据组数，每组测试数据描述如下:

在一行上输入一个整数$n(1≦n≦10^6)$代表给定的整数。

除此之外，保证单个测试文件的$n$之和不超过$10^9$。

输出描述

对于每一组测试数据，新起一行。输出一个整数，代表答案对$(10^9+7)$取模后的结果。

样例1

输入

4
2
3
10
114514

输出

3
12
396
853391453

说明

对于第二组测试数据，满足条件的二元组为$(1,2)、(1,3)、(2,3)$。他们对应的值分别为$\frac{1+2}{1}=3$、$\frac{1+3}{1}=4$、$\frac{2+3}{1}=5$，所以答案为$3+4+5=12$。