你有 $n$ 个点，你可以在这 $n$ 个点之间连无向边，两个点之间至多只能连一条边，也不允许连自环，问至多能连多少条边。

但这个问题的答案显然是 $\displaystyle \frac{n(n-1)}{2}$ 条。所以有一个额外的限制，要求这个图不存在非平凡的自同构。一个图 $G$ 有非平凡的自同构定义为存在一个 $1, 2, \ldots, n$ 的置换 $p_1, p_2, \ldots ,p_n$ 满足对于所有点 $u, v$，$(u, v)$ 之间有边当且仅当 $(p_u, p_v)$ 之间有边，并且这个置换非平凡也就是存在一个点 $u$ 使得 $p_u \ne u$。

• 比如对于一个 $5$ 个点的图 $(1,2),(2,3),(3,4),(4,5),(5,1),(1,3)$，那么 $p_1=3, p_2=2, p_3=1, p_4=5, p_5=4$ 为这个图的一个非平凡的自同构。

你要回答一个 $n$ 个点的无向简单的不存在非平凡自同构的图最多有多少条边，如果答案不存在，即不存在 $n$个点满足条件的图，请输出 -1，否则输出答案对 $10^9+7$ 的余数。

输入格式

第一行一个正整数 $T$ 表示数据组数。

接下来 $T$ 行，每行一个正整数 $n$ 表示你要回答的图的点的个数。

输出格式

共 $T$ 行，每行输出 -1 或者答案对 $10^9+7$ 的余数。

样例数据

样例输入

6
1
2
3
4
5
6

样例输出

0
-1
-1
-1
-1
9

子任务