Problem Description

There is a function $f(x)$,which is defined on the natural numbers set $N$,satisfies the following eqaution

$N^2-3N+2=\sum_{d|N} f(d)$

calulate $\sum_{i=1}^{N} f(i)$ $~mod~10^9+7$.

Input

the first line contains a positive integer T,means the number of the test cases.

next T lines there is a number N


$T \leq 500, N \leq 10^9$

only $5~$test cases has $N > 10^6$.

Output

$T$lines,each line contains a number,means the answer to the $i$-th test case.

1
3

2

$1^2-3*1+2=f(1)=0$
$2^2-3*2+2=f(2)+f(1)=0->f(2)=0$
$3^2-3*3+2=f(3)+f(1)=2->f(3)=2$
$f(1)+f(2)+f(3)=2$