题目描述

Indicium means "trace" in Latin. In this problem we work with Latin squares and matrix traces.

A Latin square is an $\mathbf{N}$-by-$\mathbf{N}$ square matrix in which each cell contains one of $\mathbf{N}$ different values, such that no value is repeated within a row or a column. In this problem, we will deal only with "natural Latin squares" in which the $\mathbf{N}$ values are the integers between 1 and $\mathbf{N}$.

The trace of a square matrix is the sum of the values on the main diagonal (which runs from the upper left to the lower right).

Given values $\mathbf{N}$ and $\mathbf{K}$, produce any $\mathbf{N}$-by-$\mathbf{N}$ "natural Latin square" with trace $\mathbf{K}$, or say it is impossible. For example, here are two possible answers for $\mathbf{N}=3, \mathbf{K}=6$. In each case, the values that contribute to the trace are underlined.

$\begin{array}{llll}\underline{2} & 1 & 3 & \underline{3} \\3 & \underline{2} & 1 & 1 \\1 & 3 & \underline{2} & 2\end{array} \begin{array}{lll}1 & 2 \\ \underline{2} & 3 \\3 & \underline{1}\end{array}$

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each consists of one line containing two integers $\mathbf{N}$ and $\mathbf{K}$ : the desired size of the matrix and the desired trace.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is IMPOSSIBLE if there is no answer for the given parameters or POSSIBLE otherwise. In the latter case, output $\mathbf{N}$ more lines of $\mathbf{N}$ integers each, representing a valid "natural Latin square" with a trace of $\mathbf{K}$, as described above.

2
3 6
2 3

Case #1: POSSIBLE
2 1 3
3 2 1
1 3 2
Case #2: IMPOSSIBLE

提示

Sample Explanation

Sample Case #1 is the one described in the problem statement.

Sample Case #2 has no answer. The only possible 2-by-2 "natural Latin squares" are as follows:

1 2 2 1
2 1 1 2

These have traces of 2 and 4, respectively. There is no way to get a trace of 3.

Limits

• $\mathrm{N} \leqslant \mathrm{K} \leqslant \mathrm{N}^{2}$.

Test set 1 (7 Pts, Visible Verdict)

• $\mathrm{T}=44$.
• $2 \leqslant \mathrm{N} \leqslant 5$.

Test set 2 (25 Pts, Hidden Verdict)

• $1 \leqslant \mathrm{T} \leqslant 100$.
• $2 \leqslant \mathrm{N} \leqslant 50$.