题目描述

用边长小于 $N$ 的正方形方砖（注意，不要求所有的方砖大小相同，请看样例说明）不重叠地铺满 $N*N$ 的正方形房间，最少要几块方砖。

输入格式

第一行是一个整数T,表示测试数据的组数,接下来的 $T$ 行，每一行是一个N($2<=N<=100$)

输出格式

对于每一组测试数据输出一行，为最少需要的块数。

样例

样例输入 1

2 
4 
5

样例输出 1

4 
8

提示

当N＝$4$ 时 

最优的铺砖方法 

AABB 

AABB 

CCDD 

CCDD 

A，$B$，$C$，$D$ 为四块方砖的代号。 

其他的铺砖方法，例如： 

AAAB 

AAAC 

AAAD 

EFGH 

需要的 $8$ 块方砖，不是最少的。