There is a $N\times N$ board. Rows and columns are numbered from $1$ to $N$. Two persons $P1$ and $P2$ randomly select two numbers $A$ and $B$ in between $2$ to $2*N$ respectively. They independently paint each block whose sum of row and column numbers is a multiple of their chosen number. The beauty of the board is equal to the number of blocks painted at least once by either one of them. Note that even if they both painted the same block, it only counts once. Print the expected beauty of the board.

Rows and columns are numbered from $1$ to $N$.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$ denoting the size of the board.

Output format

For each test case, print the expected beauty of the board in a new line. Print your answer modulo $1e9+7$.

Constraints

$1 \le T \le 100000\\ 1 \le N \le 1000000$

It is guaranteed that the sum of $N$ over $T$ test cases does not exceed $1e6$.