The University management meets every semester to discuss about the issues of the University in a round table conference. Therefore new proposals are made to the present academic curriculum. However whenever a new proposal comes from a member, all the members of the round table, except the adjacent members , throws his/her question for that proposal. It is known that every member has a proposal. Given the total no. of members in a round table meeting, you have to answer the total no. of questions thrown across the table on that particular day. Since the answer may be large, you have to print it in modulo 10^9+7.

Input

First line contains an integer t denoting the number of test cases.
Next line contains an integer n, the number of members who were present on that day.

Output
Print the answer in a new line.

Constraints

1 ≤ t ≤ 1000
1 ≤ n ≤ 10^9

Example
Input:
1
291

Output:
41904

见题面

见题面