Description

Number spiral diagonals
This problem is a programming version of Problem 28 from projecteuler.net
Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:
egin{array}{ccccc} extbf{21} & 22 & 23 & 24 & extbf{25}\ 20 & extbf{7} & 8 & extbf{9} & 10\ 19 & 6 & extbf{1} & 2 & 11 \ 18 & extbf{5} & 4 & extbf{3} & 12 \ extbf{17} & 16 & 15 & 14 & extbf{13} end{array}
It can be verified that the sum of the numbers on the diagonals is 101.
What is the sum of the numbers on the diagonals in a N imes N, (N is odd) spiral formed in the same way?
As the sum will be huge you have to print the result mod (10^9 + 7)
Input Format
The first line contains an integer T , i.e., number of test cases.
Next T lines will contain an integer N.
Output Format
Print the values corresponding to each test case.
Constraints
1 le T le 10^5
1 le N < 10^{18}, ext{N is odd}
Sample Input

Sample Output

Loading web-font TeX/Main/Bold