Description

在N ×N 的方格棋盘上放置N 个皇后，使得它们不相互攻击（即任意两个皇后都不允许同行、同列，也不允许在与棋盘边框成45角的斜线上。求有多少种合法的放置方案。

Input

输入包含多个测试用例，每个测试用例都包含一个正整数N（N ≤10），表示棋盘和皇后的数量，如果N =0，则表示结束。

Output

对每个测试用例，单行输出一个正整数，表示有多少种合法的放置方案。

Samples

1
8
5
0

1
92
10

来源

HDU2553