21645_NQueensPuzzle

The eight queens puzzle is a famous problem. We have to put eight queens on an 8 × 8 chessboard such that none of them is able to capture any other using the standard chess queen's moves (a queen can go to any place of the same row, the same column and the same diagonal). The queens must be placed in such a way that no two queens would be able to attack each other. Figure 1 shows a solution of the eight queens puzzle. For the more general N ( 8 ≤ N ≤ 300 ) queens puzzle, you should output K ( 1 ≤ K ≤ 20 ) different solutions.

Figure 1

The first line contains an integer T ( T ≤ 10 ), the number of test cases.

For each test case, the first line contains two integers N and K, indicating the size of the chessboard and the number of solutions which you should output.

For each test case, output the solutions like the samples below (each solution has N integers separated by blank characters). The solution is a permutation of { 1, 2, ..., n }. The number in the i-th place means that the i-th column queen is placed in the row with that number.

2
8 2
9 3

4 6 8 2 7 1 3 5
3 6 8 1 4 7 5 2
6 1 5 7 9 4 2 8 3
9 4 6 8 2 7 1 3 5
1 5 9 6 4 2 8 3 7