13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T7a3,

Let $$$f(i)$$$ denote the minimum positive integer $$$x$$$ such that $$$x$$$ is not a divisor of $$$i$$$.

Compute $$$\sum_{i=1}^n f(i)$$$ modulo $$$10^9+7$$$. In other words, compute $$$f(1)+f(2)+\dots+f(n)$$$ modulo $$$10^9+7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10^4$$$), the number of test cases. Then $$$t$$$ cases follow.

The only line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 10^{16}$$$).

Output

For each test case, output a single integer $$$ans$$$, where $$$ans=\sum_{i=1}^n f(i)$$$ modulo $$$10^9+7$$$.

Note

In the fourth test case $$$n=4$$$, so $$$ans=f(1)+f(2)+f(3)+f(4)$$$.

$$$1$$$ is a divisor of $$$1$$$ but $$$2$$$ isn't, so $$$2$$$ is the minimum positive integer that isn't a divisor of $$$1$$$. Thus, $$$f(1)=2$$$.

Strange Function

Examples