The One Where They Get Back Together

 F.R.I.E.N.D.S stars Jennifer Aniston, Courteney Cox, Lisa Kudrow, Matt LeBlanc, Matthew Perry and David Schwimmer have come together for the much-awaited reunion. The whole cast is going to shoot for the episode on the sets of their show. Being a huge fan, Chef's family is excited to watch the live shoot.

The set has infinite rows with infinite seats in each row for the audience. The seats are numbered starting from 1$1$ as shown in the image above. Let the seat number of the seat in the ith$i^{th}$ row and jth$j^{th}$ column be Si,j$S_{i,j}$. The price of a seat is equal to the seat number of that particular seat.

Chef wants to reserve exactly N$N$ seats for his family members such that the reserved seats form a rectangle and all the family members stay together.

Chef is allowed to choose a reduction price X$X$. After choosing the value of reduction price; if Chef has chosen the seat in the ith$i^{th}$ row and jth$j^{th}$ column, the price of this seat becomes |Si,j−X|$|S_{i,j}-X|$ for Chef. The total price of the seats selected by Chef is equal to the sum of individual prices of seats (after applying the reduction price).

Find the minimum possible total price Chef will have to pay for a selection of seats which form a rectangle of area exactly N$N$. Since this number can be huge, print it modulo (109+7${10}^9+7$).

Input Format

• First line will contain T$T$, number of testcases. Then the testcases follow.
• Each testcase contains of a single line of input, one integer N$N$, denoting the number of people in Chef's family.

Output Format

For each testcase, output in a single line the minimum price Chef has to pay for reserving N$N$ seats modulo (109+7${10}^9+7$).

Constraints

• 1≤T≤2000$1\le T\le 2000$
• 1≤N≤4∗105$1\le N\le 4\ast {10}^5$

Sample Input 1 

3
1
4
2021

Sample Output 1 

0
5
1364637

Explanation

Test case 1: One of the possible optimal selections would be seat number 5$5$ and X$X$ = 5$5$. Cost equals |seat number - X|, i.e. 0$0$.

Test case 2: Chef needs 4$4$ seats. Some possible selections are shown through rectangles in red, purple and green.

• Seats coloured in purple: [2,4,7,11]$[2,4,7,11]$. If Chef chooses X$X$ = 2$2$, Cost is |2$2$ - 2$2$| + |4$4$ - 2$2$| + |7$7$ - 2$2$| + |11$11$ - 2$2$| = 16$16$. For X$X$ = 11$11$, Cost is |2$2$ - 11$11$| + |4$4$ - 11$11$| + |7$7$ - 11$11$| + |11$11$ - 11$11$| = 20$20$.
• Seats coloured in red: [1,2,3,5]$[1,2,3,5]$. If Chef chooses X$X$ = 1$1$, Cost is |1$1$ - 1$1$| + |2$2$ - 1$1$| + |3$3$ - 1$1$| + |5$5$ - 1$1$| = 7$7$. For X$X$ = 3$3$, Cost is |1$1$ - 3$3$| + |2$2$ - 3$3$| + |3$3$ - 3$3$| + |5$5$ - 3$3$| = 5$5$. We can calculate the cost for other values of X$X$ similarly.

In this case, one of the optimal selections would be seats coloured in red, with X$X$ = 3$3$.

Click here