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