在某些民主國家中，執政黨會重劃選區以便在下次選舉時對他們有利。每個選區選出一位代表，在兩黨制的政體中，每個地區選舉的票數只要高於對手即可。
某個國家被切割成 $N\times{N}$ 個正方形區域，這些區域將會被合併為 N 個選區，每個選區包含 N 個相連的區域，這代表著我們可以上、下、左、右，移動至選區內所有的區域。
假定執政黨為 A，在野黨為 B，從上一次的選舉中，我們可以知道每個區域的投票情況。現在給你兩個 $N\times{N}$ 的矩陣，第一個是政黨 A 的投票情況，第二個則是政黨 B 的投票情況，對於每個選區，我們將包含在內所有區域的票數取總和，這時總票數多的政黨將會贏得選舉，如果兩黨的票數一樣，則此選區不會被選出代表。
現在政黨 A 僱用你去計算出，在重劃選區的情況下，最大可能的代表數差。
輸入
輸入開始於一個整數 T，代表接下來的測試組數，每組測資間不以空白行隔開。對於每組測資第一行為一整數 N，代表一個國家的規模 (N 最大為 5，而此國家有 $N\times{N}$ 個區域)，接著有 2N 行，每行有 N 個以空白格開介於 1 到 1000 的整數，前 N 行代表政黨 A 的票數，另外 N 行代表政黨 B 的票數。
輸出
輸出有 T 行，每組測資輸出一行，對於每組測資，請輸出可達到最大的代表總數的差值。
範例輸入
|
|
範例輸出
|
|