Gridtopia 城市是一个由 $R$ 行 $C$ 列方格（“街区”）组成的矩阵；行从上到下编号（从 1 开始），列从左到右编号（从 1 开始）。该城市由 $S$ 个不同的警察局负责；第 $i$ 个警察局位于第 $R_i$ 行和第 $C_i$ 列的街区中，且每个街区最多包含一个警察局。

每个警察局只能巡逻距离其水平或垂直距离不超过 $D_i$ 的街区。也就是说，第 $i$ 个警察局只能巡逻位于第 $R'$ 行和第 $C'$ 列的街区，当且仅当 $\max(|R' - R_i|, |C' - C_i|) \le D_i$。换句话说，第 $i$ 个警察局只能巡逻以该警察局为中心、边长为 $2D_i + 1$ 的正方形区域内的街区。

作为新任警察局长，你需要将城市内的一些街区分配给恰好一个能够巡逻该街区的警察局。包含警察局的街区以及没有任何警察局能够巡逻的街区不应被分配。所有其他街区都必须被分配。此外，你必须尽可能平均地在各警察局之间分配这些任务负载。令 $A_i$ 表示分配给第 $i$ 个警察局的街区数量；你的目标是最小化所有 $A_i$ 值中的最大值与最小值之差。在最优分配方案下，这个最小可能的差值是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $R$、$C$ 和 $S$：分别表示网格的行数、列数和警察局的数量。接下来有 $S$ 行，第 $i$ 行包含三个整数 $R_i$、$C_i$ 和 $D_i$：分别表示第 $i$ 个警察局所在的行、列以及决定该警察局巡逻范围的参数，如上所述。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是上述描述的差值。

数据范围

$1 \le T \le 100$。 $2 \le S \le 15$。 $1 \le R_i \le R$，对于所有 $i$。 $1 \le C_i \le C$，对于所有 $i$。 对于所有 $i \neq j$，$R_i \neq R_j$ 或 $C_i \neq C_j$。（没有两个警察局位于同一个街区。） $1 \le D_i < \max(R, C)$，对于所有 $i$。

样例

样例输入 1

2
3 4 2
1 1 1
3 3 2
5 5 2
4 1 2
3 2 2

样例输出 1

Case #1: 4
Case #2: 0

说明

在样例 1 中，城市由 3 行 4 列的网格组成，一个警察局位于左上角街区，另一个警察局位于右下角左侧的街区。第一个警察局只能巡逻与其街区相邻或对角的 3 个街区；其他所有街区与其水平或垂直距离均大于 1。第二个警察局可以巡逻网格中的任何街区（包含警察局的街区除外）。如果你将警察局 1 能巡逻的所有 3 个街区分配给它，并将剩余的 7 个街区分配给警察局 2，则分配的街区数量之差最小。

在样例 2 中，一种最优策略是按如下方式分配街区。在此图中，1 代表警察局 1，2 代表警察局 2，! 代表分配给警察局 1 的街区，@ 代表分配给警察局 2 的街区，. 代表未分配给任何警察局的街区（因为没有任何警察局能巡逻它）。注意，一个警察局分配的街区不需要形成一个连续的区域。

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