DIG - DIAGONAL

no tags 

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

hide comments
Alex Anderson: 2012-08-02 10:03:27

So in a hexagon, label the vertices 1,2,3,4,5,6. Then the intersection point between 1-4, 2-5, 3-6, counts as 3 separate intersections?

Mitch Schwartz: 2012-08-02 10:03:27

There is some issue with the input file(s). My first submission ignored T and read until EOF, but got WA.

Damian Straszak: 2012-08-02 10:03:27

This problem is not bad, but when writing a description try to avoid using abbreviations like "no".

praveen123: 2012-08-02 10:03:27

This is my first problem added on SPOJ.
For me it seems that it should go to tutorials section. I will later move it to tutorials section depending on no of accepted solutions .


Added by:praveen123
Date:2012-08-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:general problem