第一届国际鹅类会议刚刚结束，虽然这本应是一个愉快的场合，但却带有一丝苦涩。组织者发现了一份包含鸭子渗透计划细节的文件。现在，他们正试图从与会者中找出渗透小组。

他们发现的文件中包含一个由 $\mathbf{M}$ 个整数三元组 $(\mathbf{X_i}, \mathbf{Y_i}, \mathbf{C_i})$ 组成的列表，意味着鸭子们会在会议开始后恰好 $\mathbf{C_i}$ 秒在点 $(\mathbf{X_i}, \mathbf{Y_i})$ 集合，该点位于会议大厅中心以东 $\mathbf{X_i}$ 米、以北 $\mathbf{Y_i}$ 米处。每只鹅可能在也可能不在这些特定时间出现在这些特定地点，但每只鸭子肯定都在。

鸭子和鹅的最高行走速度均为每秒一米，这意味着在时间 $t$ 位于点 $(x, y)$ 的与会者，只要满足 ${\Delta_{x}}^2 + {\Delta_{y}}^2 \le {\Delta_{t}}^2$，就能在时间 $t + \Delta_{t}$ 到达点 $(x + \Delta_{x}, y + \Delta_{y})$。每位与会者在时间 $0$ 的位置可以是任意点，且与其他与会者无关。

A picture of two geese and one duck.

发现该文件后，小组举行了一次问询会议，试图识别鸭子。在会议期间，与会者依次发表了一系列陈述。按发表顺序，第 $j$ 条陈述由与会者 $\mathbf{A_j}$ 作出，声称他们自己和与会者 $\mathbf{B_j}$ 在会议开始后恰好 $\mathbf{D_j}$ 秒位于点 $(\mathbf{U_j}, \mathbf{V_j})$。陈述中的点可能是也可能不是鸭子集合的地点。

鹅的陈述总是真实的，但鸭子可能会撒谎。此外，鸭子知道哪些与会者是鸭子，哪些是鹅。为了避免轻易被抓，鸭子只会做出与鹅之前所有陈述相一致的陈述。注意，鹅所做的陈述与所有鸭子参加所有鸭子集合的情况是一致的。

仅凭提供的信息可能无法确定所有的鸭子。然而，了解鸭子的最少数量至少可以提供鸭子活动水平的下界。注意，至少有一只鸭子。请找出这个鸭子的最少数量。

形式上，一个假设 $H$ 是将所有与会者划分为鸭子集合（称为 $H$-鸭子）和鹅集合（称为 $H$-鹅）的划分。如果对于每位以不超过每秒一米的速度移动的与会者，都存在一条路径使得：

• 所有 $H$-鸭子都参加了所有鸭子集合，并且
• 对于 $S$ 中每一条声称 $A$ 在时间 $T$ 于点 $P$ 见到 $B$ 的陈述， $A$ 和 $B$ 的路径都在时间 $T$ 经过了点 $P$。

那么 $H$ 与陈述集 $S$ 是一致的。

如果满足以下条件，则假设 $H$ 在陈述集 $S$ 下是可行的：

• $H$-鸭子集合不为空（即至少有一只鸭子），
• $S$ 中由 $H$-鹅成员作出的所有陈述的子集与 $H$ 一致（即鹅的陈述总是真实的），并且
• 对于 $S$ 中由 $H$-鸭子成员作出的每一条陈述 $s$，如果 $P \subseteq S$ 是由 $H$-鹅成员在 $s$ 之前作出的陈述子集，则存在一个假设 $H'$（可能与 $H$ 相同或不同），使得 $\{ s \} \cup P$ 与 $H'$ 一致（即鸭子不会与鹅之前作出的陈述相矛盾）。

注意，$H$-鸭子包含所有与会者的假设总是可行的。

请找出所有可行假设 $H$ 中 $H$-鸭子数量的最小值。

输入格式

输入的第一行包含测试用例的数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。 每个测试用例的第一行包含三个整数 $\mathbf{N}$、$\mathbf{M}$ 和 $\mathbf{S}$，分别代表与会者人数、鸭子集合次数和陈述次数。 接下来的 $\mathbf{M}$ 行，每行描述一个不同的鸭子集合，包含三个整数 $\mathbf{X_i}$、$\mathbf{Y_i}$ 和 $\mathbf{C_i}$，表示在会议开始后恰好 $\mathbf{C_i}$ 秒在点 $(\mathbf{X_i}, \mathbf{Y_i})$ 举行了一次集合。 最后 $\mathbf{S}$ 行，每行描述一条陈述。第 $j$ 行描述第 $j$ 条陈述，包含五个整数 $\mathbf{A_j}$、$\mathbf{B_j}$、$\mathbf{U_j}$、$\mathbf{V_j}$ 和 $\mathbf{D_j}$，表示与会者 $\mathbf{A_j}$ 声称他们和与会者 $\mathbf{B_j}$ 在会议开始后恰好 $\mathbf{D_j}$ 秒位于点 $(\mathbf{U_j}, \mathbf{V_j})$。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是可能渗透会议的鸭子的最少数量。

数据范围

• $1 \le \mathbf{T} \le 50$
• $-10^9 \le \mathbf{X_i} \le 10^9$
• $-10^9 \le \mathbf{Y_i} \le 10^9$
• $1 \le \mathbf{C_i} \le 10^9$
• $\mathbf{C_i} \lt \mathbf{C_{i+1}}$
• $(\mathbf{X_i} - \mathbf{X_{i+1}})^2 + (\mathbf{Y_i} - \mathbf{Y_{i+1}})^2 \le (\mathbf{C_i} - \mathbf{C_{i+1}})^2$
• $1 \le \mathbf{A_j} \le \mathbf{N}$
• $1 \le \mathbf{B_j} \le \mathbf{N}$
• $\mathbf{A_j} \ne \mathbf{B_j}$
• $-10^9 \le \mathbf{U_j} \le 10^9$
• $-10^9 \le \mathbf{V_j} \le 10^9$
• $1 \le \mathbf{D_j} \le 10^9$
• $(\mathbf{A_j}, \mathbf{B_j}, \mathbf{U_j}, \mathbf{V_j}, \mathbf{D_j}) \ne (\mathbf{A_k}, \mathbf{B_k}, \mathbf{U_k}, \mathbf{V_k}, \mathbf{D_k})$

子任务 1

• $2 \le \mathbf{N} \le 50$
• $1 \le \mathbf{M} \le 50$
• $1 \le \mathbf{S} \le 50$

子任务 2

• $2 \le \mathbf{N} \le 10^5$
• $1 \le \mathbf{M} \le 10^5$
• $1 \le \mathbf{S} \le 10^5$

样例

输入格式 1

2
2 1 2
1 2 3
1 2 1 1 1
2 1 2 2 2
4 2 4
4 3 10
-4 -3 20
1 3 4 3 11
2 4 0 0 16
3 1 6 3 9
4 2 0 0 16

输出格式 1

Case #1: 1
Case #2: 2

说明

在样例 1 中，与会者 1 是唯一的鸭子是一个可行的假设。

在样例 2 中，与会者 2 和 4 是唯一的鸭子是一个可行的假设。

注意，至少有一只鸭子，因此所有与会者都是鹅的假设是不可行的。