問題文

1 から N までの番号のついた N 頂点からなる重み付き完全無向グラフ G があります． 頂点 i と頂点 j (1 \leq i < j \leq N) を結ぶ辺の重みは C_{i,j} です．

Alice と Bob はこれからゲームをします． まずゲームの準備として，Bob が以下の操作を行います．

• G から 0 本以上の辺を削除する．ここで削除した辺の重みの総和をコストと呼ぶことにする．
• 頂点のうち好きな A 個を選び，そこに A と書き込む．残りの N-A 個に B と書き込む．
• 好きな頂点を 1 個選び，そこに駒を 1 つ置く．

準備が終了したらゲームを開始します． Alice から始めて二人のプレイヤーは交互に手番をプレイします． 各手番では，次のいずれかの行動ができます．

• ゲームを終了する．
• 駒を隣接頂点へと動かす．ただし，今までに駒が置かれたことのある頂点へは動かせない（ゲーム開始時に駒が置かれていた頂点にも動かせない）．

ゲームが終了した瞬間に駒が置かれていた頂点に書かれた文字が A なら Alice の勝ち，B なら Bob の勝ちです． Bob は自分に必勝法が存在するようにゲームを準備したいです． そのために必要なコストの最小値を求めてください．

1 つの入力につき，T ケースを解いてください．

制約

• 1 \leq T \leq 100
• 2 \leq N \leq 20
• 1 \leq A \leq N-1
• 0 \leq C_{i,j} \leq 10^9
• T ケースにわたる N^2 の総和は 20^2 以下
• 入力はすべて整数

入力例 1

4
2 1
1
4 2
0 1 0
1 1
1
4 3
0 1 0
1 1
1
10 6
920863892 404674703 404674703 972355497 19199103 13614516 2354795 994561596 404674703
333091354 956864449 832425833 949490369 267560921 607314403 595085993 147983762
979679626 425301247 13605197 11023257 25122957 333091354 925837072
629748489 333702011 455328188 529811895 662742653 679478024
532156763 300916094 645258473 298300578 337246479
523721752 333702011 1356103 9719790
657515163 3035530 3007974
15464189 19594391
298300578

出力例 1

1
0
1
137097802

1 番目のテストケースでは，以下のようにゲームを準備すればよいです．

• 辺 (1,2) を削除する．コストが 1 かかる．
• 頂点 1,2 にそれぞれ A,B を書き込む．
• 駒を頂点 2 に置く．

2 番目のテストケースでは，以下のようにゲームを準備すればよいです．

• 辺 (1,2),(1,4) を削除する．コストが 0 かかる．
• 頂点 1,2,3,4 にそれぞれ B,A,B,A を書き込む．
• 駒を頂点 1 に置く．