```
#include<bits/stdc++.h>
using namespace std;
long long a[10000000];
int main()
{
long long mod=1e9+9;
a[1]=1;
a[2]=10;
for(long long int n=3;n<=10000000;n++)
{
a[n]=((a[n-2]%mod)+2*(2*n*n-3*n+3))%mod;
}
long long int t;
cin>>t;
while(t--)
{
long long int n;
cin>>n;
cout<<a[n]<<" ";
}
}
```

**Problem Description**

Limelight is a technique that is used when all four users take place in the cardinal directions. They will then join their strength in the form of four connecting streams above the target area. It will then create a massive ball of lightning powerful enough to incinerate everything within the area of the four users.

The Leaf village is build in the shape of Spiral of integers. Spiral of integers, of an integer N, is an interesting NN spiral matrix which starts with 1 at the center.

For example, for N=4, the spiral of integers is Kitane, Nauma, Tu and Seito are planning to destroy the whole Leaf village. The limelight spot will be the 4 corners of the village.

Strength of the attack is equal to the sum of all the elements in the connecting streams as shown in the figure ( sum of diagonal elements of the spiral of integers of N ) .

Given the value of N, you need to compute the strength of the attack (mod 10^9+9).

Input:

First line contains an integer T, denoting the number of test cases.

Each test case consists of a single integer N.

Output:

For each test case output a single integer denoting the strength of the attack (mod 10^9+9).

Constraints:

1<=T<=10^5

1<=N<=10^7**Test Case 1**

**Input (stdin)**2

4 10000000

**Expected Output**56 679604006**Test Case 2**

**Input (stdin)**30

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

**Expected Output**1 10 25 56 101 170 261 384 537 730 961 1240 1565 1946 2381 2880 3441 4074 4777 5560 6421 7370 8405 9536 10761 12090 13521 15064 16717 18490