Description

Indicium 在拉丁语中意为"迹"。本题中我们将研究拉丁方阵及其矩阵迹。

一个拉丁方阵是指 $\mathbf{N} \times \mathbf{N}$ 的方阵，其中每个单元格包含 $\mathbf{N}$ 个不同值之一，且每行每列都不重复出现相同值。在本题中，我们仅处理"自然拉丁方阵"，即这些 $\mathbf{N}$ 个值为 1 到 $\mathbf{N}$ 的整数。

方阵的迹是指主对角线（从左上到右下）上所有值的和。

给定 $\mathbf{N}$ 和 $\mathbf{K}$，构造任意一个迹为 $\mathbf{K}$ 的 $\mathbf{N} \times \mathbf{N}$ 自然拉丁方阵，或判定其不存在。例如，以下是 $\mathbf{N}=3, \mathbf{K}=6$ 时的两种可能解（贡献迹的值已加下划线）：

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

Input Format

输入第一行包含测试用例数 $\mathbf{T}$。随后 $\mathbf{T}$ 行，每行包含两个整数 $\mathbf{N}$ 和 $\mathbf{K}$，分别表示方阵大小和期望的迹。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为 IMPOSSIBLE（无解时）或 POSSIBLE（有解时）。若有解，还需输出 $\mathbf{N}$ 行，每行 $\mathbf{N}$ 个整数表示满足条件的自然拉丁方阵。

2
3 6
2 3

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

Hint

样例解释

样例 #1 对应题目描述中的情况。

样例 #2 无解。所有可能的 2×2 自然拉丁方阵如下：

1 2 2 1
2 1 1 2

它们的迹分别为 2 和 4，无法得到迹 3。

数据范围

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

测试集 1（7 分，可见判果）

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

测试集 2（25 分，隐藏判果）

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

翻译由 DeepSeek V3 完成