Kings on a Chessboard

Place a maximum number of kings on an n × n chessboard (0 < n < 11) so that no kings attack each other. The king attacks its adjoining squares. Determine the maximum number of kings which can be put on the chessboard and the number of possible ways they can be placed based on the input data.

Input Specification

The first line of the input contains an integer t, which is the number of test cases. The next t lines contain t different test cases with an integer n, representing n from the problem description.

Output Specification

The first line of a test case should contain the maximum number of kings which can be placed on the chessboard, the second line should contain the number of possibilities. Print an empty line between successive test cases.

Sample Input

1. 3
2. 2
3. 4
4. 3

download as text file

Output for Sample Input

1. 1
2. 4
4. 4
5. 79
7. 4
8. 1

download as text file