11979 - Hamming Base

給定N個以N進制表示的整數，每個整數有M個位數(包含前導的零)，我們定義兩個整數為「K階相似(K-similar)」表示他們剛好有K個位數值是一樣的，例如321與213為零階相似，3456與6453與二階相似，123與453與一階相似。你的目標是一步步改變這N個整數，使得任兩個整數為零階相似，每一步限定為只能改變某個整數的某個位數，使其加一或減一，當該位數值為0則無法作減一的動作，若為N-1則無法做加一的動作。

請你用最少的步驟來達成這項目標。

Input

輸入的一開始會給定整數T(<= 50)表示測試資料的組數。每組資料的第一列有兩個整數N(2 <= N <= 2000)與M(1 <= M <= 10)，接下來的N列每列有M個其值介於 0 ~ N-1 的整數，每列的M個整數組成有M個位數，且以N進制表示的整數。

Output

請每組測試資料輸出資料編號與達成這項目標的最少步驟數。

Sample Input	Output for Sample Input
2 3 3 0 0 0 0 0 0 0 0 0 4 2 0 0 0 0 0 2 2 0	Case 1: 9 Case 2: 8

---

原文出處