Description

给定一整数n, 写递归函数求3f(ceil(n/3))+n*n, 其中ceil(n/3)表示向上取整，f(0)=1, f(1)=1.

Input

输入第1行有一个int型正整数m (m<＝20), 表示有m行输入.
每行输入一个int型正整数n (1000<n<10000).

Output

输出m行, 每行为3f(ceil(n/3))+n*n.

Sample Input

5
3
4
9294
9053
1431

Sample Output

12
37
129653355
123029056
3073815