Leaf and Limelight Attack
Tag(s):

## Dynamic Programming, Easy

Problem
Editorial
Analytics

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$).

Input:

First line contains an integer $T$, denoting the number of testcases.
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 \le T \le 10^5$
$1 \le N \le 10^7$

SAMPLE INPUT
2
4
10000000
SAMPLE OUTPUT
56
679604006

Explanation

First test case: Sum of the diagonal elements will be $16 + 4 + 2 + 10 + 13 + 3 + 1 + 7 = 56.$

Second test case: Happy Coding :)

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

June Circuits

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Algorithms > Graphs