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 (no of test cases)

Next T line will contain N no of vertices

Output

No of intersections of diagonals as specified.

Example

Input:
2
4
5
 Output:

1
5