Description

You have $n$ vertices. You may add undirected edges between these $n$ vertices, with at most one edge per pair and no self-loops. What is the maximum number of edges you can add?

The obvious answer is $\dfrac{n(n-1)}{2}$ edges. Therefore, there is an additional constraint: the graph must not have a nontrivial automorphism.

A graph $G$ has a nontrivial automorphism if there exists a permutation $p$ of $\{1, \dots, n\}$ such that for all vertices $u, v$, there is an edge between $u$ and $v$ if and only if there is an edge between $p(u)$ and $p(v)$, and this permutation is nontrivial, i.e., there exists a vertex $u$ with $p(u) \ne u$.

For example, for the 5-vertex graph $(1,2),(2,3),(3,4),(4,5),(5,1),(1,3)$, the mapping $p(1)=3$, $p(2)=2$, $p(3)=1$, $p(4)=5$, $p(5)=4$ is a nontrivial automorphism of this graph.

You need to answer: among simple undirected graphs on $n$ vertices that have no nontrivial automorphism, what is the maximum number of edges? If no such graph on $n$ vertices exists, output -1; otherwise, output the answer modulo $10^9+7$.

Input Format

This problem contains multiple test cases.
A single line with a positive integer $T$, the number of test cases.
For each test case:
A single positive integer $n$, the number of vertices.

Output Format

For each test case:
Output a single integer, the answer modulo $10^9+7$. If no graph on $n$ vertices satisfies the condition, output -1.

6
1
2
3
4
5
6

0
-1
-1
-1
-1
9

Hint

For $100\%$ of the testdata, $1 \le n \le 10^{100}$, $1 \le T \le 10^4$.

Translated by ChatGPT 5