E - K-Independent Matrix Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

正の整数 N が与えられます。

1 以上 N 以下の整数からなる N \times N 行列 A であって、以下の条件を満たすものを 1 つ構築してください。

  • 各 K = 1, 2, \ldots, N に対して以下が成り立つ。
    • A の任意の K \times K の小正方形には、K の倍数である要素がちょうど 1 つ存在する。

ここで、K \times K の小正方形とは、行列 A から連続する K 行と連続する K 列を選ぶことで得られる部分行列を指します。

本問題の制約下では、条件を満たす行列 A が必ず存在することを証明できます。

T 個のテストケースについて答えてください。

制約

  • 1 \le T \le 10^5
  • 1 \le N \le 1000
  • 全てのテストケースにおける N^2 の総和は 10^6 以下
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N

出力

各テストケースについて、条件を満たす行列 A を以下の形式で出力せよ。

A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

条件を満たす行列が複数存在する場合、どれを出力しても正解となる。

入力例 1

3
3
4
1

出力例 1

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

1 個目のテストケースについて、出力された行列

A = \begin{pmatrix} 1 & 1 & 2 \\ 2 & 1 & 1 \\ 1 & 3 & 2 \end{pmatrix}

は条件を満たします。実際、

  • K = 1 について、A のどの 1 \times 1 の小正方形にも、1 の倍数である要素がちょうど 1 つ存在します。
  • K = 2 について、A のどの 2 \times 2 の小正方形にも、2 の倍数である要素がちょうど 1 つ存在します。
  • K = 3 について、A の 3 \times 3 の小正方形、すなわち A 自身には、3 の倍数である要素がちょうど 1 つ存在します。

以上より、条件を満たしていることが確認できます。

条件を満たす行列は他にも存在しますが、どれを出力しても正解となります。