The rules of the checkers game is very simple: First, the number of participants in the game is even -- two, four or six peoples. Then you play with the diagonal player. Chesses can move one step in a straight line to the adjacent 6 directions. If adjacent location has a chess, and the next adjacent location is empty in the same line, then your chess can directly “jump” to the empty location. In the process of “jump”, as long as meeting the same conditions that is defined above, you can “jump” consecutively. The first player who occupies all the oppositive positions wins.
Figure 1:
Oaiei is tired of playing with others, he want to play himself. His game’s rules is showed as follows:
When the size of chessboard N is 7，the initial state is showed as following:
The end state is showed as following:
Now,your task is coming. Give you the size of chessboard N, and you should compute the minimum move steps that can change the initial state into the end state.
There are multiple test cases. Each test case contains a positive odd integer N (N<20) indicating the size of chessboard.
For each test case, print the integer number which indicting the minimum move steps.
If the chessboard size is five, then one of solutions with least number of steps is showed as following: