AT_arc222_c [ARC222C] 2 Directions vs 4 Directions

$ N\times N $ のマス目があります．ここで $ N $ は $ 2 $ 以上の整数です． $ 1\leq i,j\leq N $ に対して，上から $ i $ 行目，左から $ j $ 列目のマスを $ (i,j) $ で表します． はじめ，すべてのマスは黒マスです．また各マス $ (i,j) $ について，マスの色を黒から白に変更するためのコスト $ A_{i,j} $ が与えられます． このマス目とひとつの駒を使って，Alice と Bob がゲームを行います．ゲームは次のような $ 3 $ つのステップからなります． #### ステップ 1 審判が，駒を最初に置くマスを指定します． #### ステップ 2 Alice は次の操作を $ 0 $ 回以上行います． - 黒マス $ (i,j) $ をひとつ選び，コスト $ A_{i,j} $ を支払って，そのマスを白マスに変更する． #### ステップ 3 ステップ 1 で初期位置として指定されたマスに駒を置きます．その後 Alice から始めて，Alice と Bob は交互に手番を行います． - Alice の手番では，Alice が駒を**左右**のいずれかに隣接するマスへ動かす． - Bob の手番では，Bob が駒を**上下左右**のいずれかに隣接するマスへ動かす． ただし，マス目の外へ出るように動かすことはできません． ステップ 3 は，Alice と Bob がそれぞれ $ 10^{10} $ 回ずつ手番を行った直後に終了します． ステップ 3 が終了した時点で，駒があるマスが白マスならば Alice の勝ち，黒マスならば Bob の勝ちとなります．Alice と Bob はステップ 3 において，それぞれ自分が勝つために最適に行動します． 各マス $ (h,w) $ について，ステップ 1 で駒を最初に置くマスとして $ (h,w) $ が指定された場合に，Alice が勝つためにステップ 2 で支払う必要がある合計コストの最小値を求めてください． $ T $ 個のテストケースが与えられるので，それぞれについて答えを求めてください．

入力は以下の形式で標準入力から与えられます． > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられます． > $ N $ $ 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} $

テストケースごとに $ N $ 行出力してください． 各テストケースにおける $ h $ 行目には， $ (h,1),(h,2),\ldots,(h,N) $ が指定された場合に，Alice が勝つためにステップ 2 で支払う必要がある合計コストの最小値を，空白区切りで出力してください．

### Sample Explanation 1 $ 1 $ 番目のテストケースについて説明します． $ (h,w) = (1,1) $ または $ (h,w) = (2,2) $ の場合には，Alice はマス $ (1,1), (2,2) $ を白マスに変更します． この場合，Bob が手番を終えるたびに，駒は $ (1,1) $ または $ (2,2) $ にあります．したがって Alice と Bob がそれぞれ $ 10^{10} $ 回ずつ手番を行った直後には駒が $ (1,1) $ または $ (2,2) $ にあるため，どのように駒を動かしても，Alice の勝ちとなります．Alice がステップ 2 で支払うコストは， $ A_{1,1}+A_{2,2}=1+2=3 $ です． $ (h,w) = (1,2) $ または $ (h,w) = (2,1) $ の場合にも，Alice はマス $ (1,2), (2,1) $ を白マスに変更することで勝てることが確かめられます．この場合，Alice がステップ 2 で支払うコストは， $ A_{1,2}+A_{2,1}=4+3=7 $ です． ### Constraints - $ 1\leq T\leq 10^4 $ - $ 2\leq N\leq 500 $ - $ 0\leq A_{i,j}\leq 10^9 $ - 入力される値はすべて整数． - すべてのテストケースにわたる $ N^2 $ の総和は $ 500^2 $ 以下．