관할 구역 제한

Gridtopia시는 R개의 행과 C개의 열로 이루어진 정사각형 칸(이하 "블록")의 행렬이다. 행은 위에서 아래로 (1부터 시작하여) 번호가 매겨지고, 열은 왼쪽에서 오른쪽으로 (1부터 시작하여) 번호가 매겨진다. 이 도시에는 S개의 서로 다른 경찰서가 있다. i번째 경찰서는 $R_{i}$번째 행과 $C_{i}$번째 열에 위치한 블록에 있으며, 어느 블록에도 둘 이상의 경찰서가 있지 않다.

각 경찰서는 가로나 세로 방향으로 그 경찰서에서 $D_{i}$블록 이하만큼 떨어진 블록만 순찰할 수 있다. 즉, i번째 경찰서는 max(|R' - $R_{i}$|, |C'- $C_{i}$|) ≤ $D_{i}$인 경우에만 R'행 C'열의 블록을 순찰할 수 있다. 달리 말하면, i번째 경찰서는 해당 경찰서를 중심으로 하는 한 변의 길이가 2D_{i} + 1인 정사각형 안의 블록만 순찰할 수 있다.

새 경찰청장인 당신은 도시 안의 일부 블록을 그 블록을 순찰할 수 있는 정확히 하나의 경찰서에 배정해야 한다. 경찰서가 있는 블록과 어느 경찰서도 순찰할 수 없는 블록은 배정하지 않아야 한다. 그 밖의 모든 블록은 배정해야 한다. 또한 이 배정 부담을 경찰서들 사이에 가능한 한 균등하게 분배해야 한다. $A_{i}$를 i번째 경찰서에 배정된 블록 수라고 하자. 그러면 모든 $A_{i}$ 값의 최댓값과 모든 $A_{i}$ 값의 최솟값의 차이를 최소화하는 것이 목표이다. 최적으로 배정했을 때 가능한 가장 작은 차이는 얼마인가?

제한

1 ≤ T ≤ 100. 2 ≤ S ≤ 15. 모든 i에 대해, 1 ≤ $R_{i}$ ≤ R. 모든 i에 대해, 1 ≤ $C_{i}$ ≤ C. 모든 i ≠ j에 대해, $R_{i}$ ≠ $R_{j}$ 및/또는 $C_{i}$ ≠ $C_{j}$. (서로 같은 블록에 있는 두 경찰서는 없다.) 모든 i에 대해, 1 ≤ $D_{i}$ < max(R, C). 시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

1 ≤ R ≤ 20. 1 ≤ C ≤ 20.

테스트 세트 2 (비공개)

1 ≤ R ≤ $10^{9}$. 1 ≤ C ≤ $10^{9}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 R, C, S가 있는 한 줄로 시작한다. 이들은 각각 블록 격자의 행 수와 열 수, 그리고 경찰서 수이다. 그다음 S개의 줄이 더 주어진다. 이 중 i번째 줄에는 세 정수 $R_{i}$, $C_{i}$, $D_{i}$가 주어진다. 이들은 각각 i번째 경찰서가 위치한 행과 열, 그리고 위에서 설명한 대로 그 경찰서가 순찰할 수 있는 블록을 결정하는 매개변수이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 위에서 설명한 차이이다.

예제 케이스 #1에서 도시는 3개의 행과 4개의 열로 이루어진 격자이며, 왼쪽 위 블록에 경찰서 하나가 있고 오른쪽 아래 블록의 왼쪽 블록에 경찰서 하나가 있다. 첫 번째 경찰서는 자신의 블록과 변 또는 꼭짓점이 맞닿은 세 블록만 순찰할 수 있다. 그 밖의 모든 블록은 가로 또는 세로 방향 거리가 1보다 크다. 두 번째 경찰서는 (경찰서가 있는 블록을 제외하고) 격자의 어느 블록이든 순찰할 수 있다. 경찰서 1에 순찰할 수 있는 세 블록을 모두 배정한 다음, 남은 일곱 블록을 경찰서 2에 배정하면 배정된 블록 수의 차이가 최소화된다.

예제 케이스 #2에서 한 가지 최적 전략은 다음과 같이 블록을 배정하는 것이다. 이 그림에서 1는 경찰서 1을, 2는 경찰서 2를, !는 경찰서 1에 배정된 블록을, @는 경찰서 2에 배정된 블록을, .는 (어느 경찰서도 순찰할 수 없어서) 어느 경찰서에도 배정되지 않은 블록을 나타낸다. 한 경찰서에 배정된 블록들이 하나의 연속된 영역을 이룰 필요는 없다는 점에 유의하라.

@@@@. !!!@. !2!@. 1!!@. !@!@.