你在一个虚幻的空间中行走，周围的一切是如此不真实，你渐渐意识到自己正身在梦里……在梦的世界中，地面是一个边界在无穷远处的方格矩阵。你可以朝前后左右任意方向前进，但当你离开当前方格时，该方格会立即塌陷，而你将永远无法回到那里。如果现在允许你走N步（移动到相邻方格算作一步），你能否计算出共有多少种不同的路线方案？

多组测试用例。第一行为一个整数T（0<T<=25），之后依次给出T组测试用例。

每组测试用例仅一行，包含一个整数N（0<=N<=24），表示允许在方格上行走的步数。

对于每组测试用例，输出可行的路线方案总数。两个方案不同当且仅当存在至少一步走法不同。

2

1

2

4
12