Програмчлалын олимпиадын бодлогын архив

Хэсэг сөрөг биш бүхэл тоонууд өгөгджээ. Тэдгээрийн дурын нэгийг сонгон авч 1-ээр нэмэгдүүлэх болон хорогдуулах үйлдэл хийхийг зөвшөөрчээ. Тэгвэл тэдгээр тоонуудыг хамгийн багадаа хэдэн үйлдлээр бүгдийг ялгаатай болгохыг тогтоох програм зохионо уу!

Input

Оролтын файлын эхний мөрөнд тестийн тоо T өгөгдөнө. Тест нь дараах бүтэцтэй.
Тестийн эхний мөрөнд N ба M (1<=N<=2000,1<=M<=10) тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. Дараагийн N тооны мөр тус бүрд M ширхэг сөрөг бус бүхэл A_i (0<= A_i<=N-1)тоонууд нэг хоосон зайтайгаар тусгаарлагдан байрлана. Таны даалгавар бол M тооны багана бүрийн элементүүдийг ялгаатай болгоход шаардагдах нийт үйлдлийн тоог олох байна. Хэрэв A_i-нь 0 болбол хорогдуулах , N-1 болбол нэмэгдүүлэх үйлдлийг тус тус хийх боломжгүй гэдгийг анхаарна уу!

Output

Тест бүрд харгалзах хариуг нэг нэг мөрөнд гаргах бөгөөд хариу нь багана бүрийн элементүүдийг ялгаатай болгоход шаардагдах үйлдлүүдийн нийт тоо байна.

Example

Input:
2
 4 2
 0 0
 0 2
 2 0
 0 0
 2 3
 1 0 1
 1 0 0

Output:
8
 2

Тайлбар:2-р тестийн эхний багананд аль нэг нэгийг 1-ээр хорогдуулна. Харин хоёрдугаар баганын хувьд аль 

нэг 0-ийг 1-ээр нэмэгдүүлнэ. Сүүлийн багананд үйлдэл хийх шаардлагагүй тиймээс нийт үйлдлийн тоо буюу гаралт нь 2 байна.

Г. Багаболд