对于符号三角形问题，符号三角形的第一行有n个符号。符号可以为“＋”或“－”，以下每一行的符号由上行得到，2个同号下面都是“+”，2个异号下面都是“－”。如下图所示（第一行有4个符号的符号三角中的其中的一个）：









符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“＋”和“－”的个数相同。







Input



输入包含若干个测试用例。

对于每个测试用例，输入的一行是一个整数n(2<=n<=20)，表示符号三角形第一行符号的个数。当输入n为0时表示输入结束。





Output



对于每个测试案例，输出包括一行，这一行只包含一个整数，就是该测试案例总共有多少不同的符号三角形，使其所含的“＋”和“－”的个数相同。



Sample Input





2

3

0



Sample Output





0

4