제어된 공기 주입

주유소의 공기 펌프 대기 줄이 너무 길어지고 있다! 고객들이 타이어, 스포츠 공, 거대한 퍼레이드용 풍선 동물 인형과 그 밖의 제품에 더 빠르게 공기를 넣을 수 있도록 과정을 최적화하려 한다.

펌프는 자동이다. 압력을 특정 파스칼 값으로 설정하고 공기를 넣을 제품에 펌프를 연결하면, 필요에 따라 정확히 그 압력까지 공기가 주입된다. 펌프에는 올림과 내림, 두 개의 버튼만 있다. 이 버튼들은 목표 압력을 각각 정확히 $1$파스칼만큼 높이거나 낮춘다.

$\mathbf{N}$명의 고객이 줄을 서 있으며, 각 고객은 펌프로 공기를 넣어야 하는 제품을 정확히 $\mathbf{P}$개씩 가져온다. 각 제품의 목표 압력을 알고 있다. 한 고객의 제품들은 원하는 순서대로 공기를 넣을 수 있지만, 고객의 순서는 바꿀 수 없다. 구체적으로, $(i + 1)$번째 고객의 제품 중 어느 하나에라도 공기를 넣기 전에 $i$번째 고객의 모든 제품에 공기를 넣어야 한다. 두 제품을 연이어 처리할 때 두 제품의 목표 압력이 서로 다르다면 펌프의 버튼을 사용해야 한다.

펌프는 처음에 $0$파스칼로 설정되어 있으며, 모든 고객의 모든 제품에 공기를 넣은 뒤에는 어떤 값으로 남겨 두어도 된다. 각 고객의 제품 순서를 최적으로 정할 때 필요한 버튼 누름 횟수의 최솟값은 얼마인가?

제한

시간 제한: 5초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i, j$에 대해 $1 \le \mathbf{X_{i,j}} \le 10^9$.

테스트 세트 1 (Visible Verdict)

$2 \le \mathbf{N} \le 10$. $2 \le \mathbf{P} \le 3$.

테스트 세트 2 (Hidden Verdict)

$2 \le \mathbf{N} \le 1000$. $2 \le \mathbf{P} \le 100$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 고객 수와 각 고객이 가져오는 제품 수를 각각 나타내는 두 정수 $\mathbf{N}$와 $\mathbf{P}$가 포함된 줄로 시작한다. 이어서 $\mathbf{N}$개의 줄이 주어진다. 이 줄들 중 $i$번째 줄에는 $\mathbf{P}$개의 정수 $\mathbf{X_{i,1}}, \mathbf{X_{i,2}}, \dots, \mathbf{X_{i,P}}$가 주어지며, 이는 $i$번째 고객이 가져온 $j$번째 제품의 목표 압력이 $\mathbf{X_{i,j}}$파스칼임을 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 모든 제품을 지정된 압력에 맞게 팽창시키는 데 필요한 버튼 누름 횟수의 최솟값이다.

예제 케이스 #1에서 펌프를 사용하는 최적의 방법 중 하나는 다음과 같다.

• 올림 버튼을 $10$번 눌러 펌프를 $10$로 설정하고, $10$파스칼이 필요한 제품(고객 1의 제품)에 공기를 넣는다.

• 올림 버튼을 $30$번 눌러 펌프를 $40$로 설정하고, $40$파스칼이 필요한 제품(고객 1의 제품)에 공기를 넣는다.

• 내림 버튼을 $10$번 눌러 펌프를 $30$로 설정하고, $30$파스칼이 필요한 제품(고객 1의 제품)에 공기를 넣는다.

• 내림 버튼을 $10$번 눌러 펌프를 $20$로 설정하고, $20$파스칼이 필요한 제품(고객 2의 제품)에 공기를 넣는다.

• 올림 버튼을 $30$번 눌러 펌프를 $50$로 설정하고, $50$파스칼이 필요한 제품(고객 2의 제품)에 공기를 넣는다.

• 올림 버튼을 $10$번 눌러 펌프를 $60$로 설정하고, $60$파스칼이 필요한 제품(고객 2의 제품)과 두 제품(고객 3의 제품)에 공기를 넣은 뒤, 마지막으로

• 내림 버튼을 $10$번 눌러 펌프를 $50$로 설정하고, $50$파스칼이 필요한 제품(고객 3의 제품)에 공기를 넣는다.

버튼을 누르는 총횟수는 $110$번이다.

예제 케이스 #2에서는 답이 $2^{32}$보다 클 수 있음에 유의한다.