“如果您愿意的话，让我带您去吧，这颗星球，愿望实现的地方……”
     在cayun星球的中央，有着一扇通往幻想世界的大门，然而这扇大门的钥匙却很奇怪，它不是固定的：大门会首先给你一个数字a，然后钥匙就是另一串数字b。
     根据那些很厉害的cayun们的长期研究，cayun们终于发现，数字b即为下面这个问题的答案：有如下一个图形，每个小方格均为正方形，对于边长为a（下图边长为3）的图形，钥匙b即为用准确a个矩形来填充的方案数。
 
    听说在幻想世界中都有着许许多多的折射着主世界的光玉，于是某个顽皮的搞事cayun决定去幻想世界旅行，但是由于智商只有三岁，所以只能求助于大佬星球的你。

第一行数据组数T(T<=25)

对于每组数据，只有一个正整数n(1 <= n <= 25)，代表边长

每组数据一行，代表钥匙b

边长为4的有如下14种：