Again let's imagine a knight on a chessboard.
Recall that a knight's move involves moving 2 spaces along one axis, then 1 space along the other axis.
After a single move, there are 8 possible squares the knight could end up on.
Because after his first move there are 9 possible squares the knight may have travled through (including the starting square), we say that the knight's Range after his first move is 9. After move 2, the knight's range increases to 41.
After 2 moves, the there are 41 squares the knight could have traveled through.
Problem Statement
Given an integer, determine the knight's range after that many moves.
Input Data
The first line will be Q, the quantity of testcases.
Q space-separated values will follow, each a single integer n.
Answer
Should consist of Q space-separated integers, corresponding to the range of the knight after n turns in each testcase.
Example
input data:
3
1
2
1234
answer:
9 41 21311185