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^9 + 7 , take modulo 10^9 + 7

1<=n<=10^8

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