SP11274 LIGHTPZ - Lights and Switches

在生日那天，Perrin 收到了一份特别的谜题。这个谜题是一个 $N \times N$ 的灯泡网格，所有灯泡最初都是熄灭状态。你的任务是打开一些灯泡，使每行和每列有且仅有一个灯泡被点亮。虽然这个任务看起来简单，但有一个附加限制：每个灯泡只能在一个特定的关键时间点打开。由于 Perrin 很忙，不想在这个谜题上耗费太多时间。请你帮助 Perrin 计算完成这个目标所需的最少时间间隔。注意，这个时间间隔是第一个灯泡被点亮和最后一个灯泡被点亮的时间之差。

第一行是整数 $T$，表示有 $T$ 个测试用例。 接下来是每个测试用例的具体数据。对于每个测试用例，第一行是整数 $N$。接下来的 $N$ 行，每行包含 $N$ 个整数。这第 $i$ 行的第 $j$ 个整数表示第 $i$ 行、第 $j$ 列的灯泡的关键时间。 所有灯泡的关键时间都是不相同的。

输出 $T$ 行，每行有一个整数，表示对应测试用例下完成目标所需的最小时间间隔。

- $1 \le T \le 10$ - $1 \le N \le 15$ - $1 \le \text{关键时间} \le 10^9$ **本翻译由 AI 自动生成**