Description

一个骑士（也就是马）在无限大的国际象棋棋盘中跳，问跳不超过\(n\)步能跳到多少个不同的格子。
不知道马怎么跳的问一下周围同学。

Format

Input

第一行一个正整数\(T(T<=100000)\)表示数据组数
接下来\(T\)行每行一个正整数\(n(0<=n<=10^9)\)，表示步数。

Output

按照输入顺序，对于每组数据，输出能跳到的格子数。

Sample 1

Input

3
0
1
7

Output

1
9
649

Limitation

1s, 64MB for each test case.

Source

Vijos Original