You are a given a n sided convex polygon. Find total number of intersections of all diagonals.

Assume that all the intersection points are different.

If in case answer exceeds 10⁹ + 7 , take modulo 10⁹ + 7

1 ≤ n ≤ 10⁸

Input

First Line : T (number of test cases.)

Next T line will contain N number of vertices.

Output

Number of intersections of diagonals as specified.

Example

Input:
2
4
5

Output:
1
5