Fermat's Little Theorem#3723

Fermat's Little Theorem

4 seconds

256 megabytes

Hard

Fermat's Little Theorem tells us that for any prime number $p$ and any integer $a$ , the expression $a^{p} - a$ a^p - a is divisible by $p$ . In this problem, we explore a similar concept.

Given a natural number $n > 1$ n > 1, your task is to identify all natural numbers $m$ such that $a^{n} - a$ a^n - a is divisible by $m$ for every integer $a$ .

For example, when $n = 2$ n = 2, there are $2$ such numbers: $1$ and $2$ . When $n = 3$ n = 3, there are $4$ such numbers: $1$ , $2$ , $3$ , and $6$ . Since there may be many such numbers, compute the sum of all these numbers modulo $1 0^{9} + 7$ 10^9 + 7.

It is guaranteed that for any $n > 1$ n > 1, the set of such numbers is finite.

Input

The first line contains a natural number $T$ ( $1 \leq T \leq 1 0^{5}$ 1 \leq T \leq 10^5) — the number of test cases.

Each of the following $T$ lines contains an integer $n$ ( $2 \leq n \leq 2 \times 1 0^{6}$ 2 \leq n \leq 2 \times 10^6).

Output

For each $n$ given in the input, output the answer on a separate line.

Examples

Example

2
2
3

3
12

Example 1

Note

For $n = 2$ n = 2, the valid values of $m$ are $1$ and $2$ . The sum is $1 + 2 = 3$ 1 + 2 = 3.

For $n = 3$ n = 3, the valid values of $m$ are $1$ , $2$ , $3$ , and $6$ . The sum is $1 + 2 + 3 + 6 = 12$ 1 + 2 + 3 + 6 = 12.