设 $$$f(i)$$$ 表示最小正整数 $$$x$$$,使得 $$$x$$$ 不是 $$$i$$$ 的约数。
计算 $$$\sum_{i=1}^n f(i)$$$ 模 $$$10^9+7$$$。换句话说,计算 $$$f(1)+f(2)+\dots+f(n)$$$ 模 $$$10^9+7$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$),即测试用例的数量。然后是 $$$t$$$ 案例。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 10^{16}$$$)。
输出
对于每个测试用例,输出一个整数 $$$ans$$$,其中 $$$ans=\sum_{i=1}^n f(i)$$$ 模 $$$10^9+7$$$。
示例
输入 #1
6 1 2 3 4 10 10000000000000000
输出 #1
2 5 7 10 26 366580019
注意
在第四个测试用例 $$$n=4$$$ 中,因此 $$$ans=f(1)+f(2)+f(3)+f(4)$$$。
- $$$1$$$ 是 $$$1$$$ 的约数,但 $$$2$$$ 不是,因此 $$$2$$$ 是不是 $$$1$$$ 的约数的最小正整数。因此,$$$f(1)=2$$$。
- $$$1$$$ 和 $$$2$$$ 是 $$$2$$$ 的约数,但 $$$3$$$ 不是,因此 $$$3$$$ 是不是 $$$2$$$ 的约数的最小正整数。因此,$$$f(2)=3$$$。
- $$$1$$$ 是 $$$3$$$ 的约数,但 $$$2$$$ 不是,因此 $$$2$$$ 是不是 $$$3$$$ 的约数的最小正整数。因此,$$$f(3)=2$$$。
- $$$1$$$ 和 $$$2$$$ 是 $$$4$$$ 的约数,但 $$$3$$$ 不是,因此 $$$3$$$ 是不是 $$$4$$$ 的约数的最小正整数。因此,$$$f(4)=3$$$。
因此,$$$ans=f(1)+f(2)+f(3)+f(4)=2+3+2+3=10$$$。