You have $n$ vertices. You can add undirected edges between these $n$ vertices, with at most one edge between any two vertices and no self-loops. You want to know the maximum number of edges you can add.

The answer to this problem is obviously $\displaystyle \frac{n(n-1)}{2}$. Therefore, there is an additional constraint: the graph must not have any non-trivial automorphisms. A graph $G$ has a non-trivial automorphism if there exists a permutation $p_1, p_2, \ldots, p_n$ of $1, 2, \ldots, n$ such that for all vertices $u, v$, there is an edge between $(u, v)$ if and only if there is an edge between $(p_u, p_v)$, and the permutation is non-trivial, meaning there exists at least one vertex $u$ such that $p_u \neq u$.

• For example, for a graph with $5$ vertices and edges $(1,2), (2,3), (3,4), (4,5), (5,1), (1,3)$, the permutation $p_1=3, p_2=2, p_3=1, p_4=5, p_5=4$ is a non-trivial automorphism of the graph.

You need to answer the maximum number of edges in an undirected simple graph with $n$ vertices that has no non-trivial automorphisms. If no such graph exists for $n$ vertices, output -1. Otherwise, output the answer modulo $10^9+7$.

Input

The first line contains a positive integer $T$, representing the number of test cases.

Each of the next $T$ lines contains a positive integer $n$, representing the number of vertices in the graph.

Output

Output $T$ lines, each containing either -1 or the answer modulo $10^9+7$.

Examples

Input 1

6
1
2
3
4
5
6

Output 1

0
-1
-1
-1
-1
9

Subtasks