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 $$N * N$$ spiral matrix which starts with $$1$$ at the center. For example, for $$N = 4$$, the spiral of integers is
16 15 14 13 5 4 3 12 6 1 2 11 7 8 9 10
Kitane, Nauma, Tōu 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$$).
First line contains an integer $$T$$, denoting the number of testcases.
Each test case consists of a single integer $$N$$.
For each test case output a single integer denoting the strength of the attack (mod $$10^9 + 9$$).
$$1 \le T \le 10^5$$
$$1 \le N \le 10^7$$
First test case: Sum of the diagonal elements will be $$16 + 4 + 2 + 10 + 13 + 3 + 1 + 7 = 56.$$
Second test case: Happy Coding :)