距离 Sphinny 成为顶尖编程选手并掌握竞赛调度艺术已经过去了近 15 年。她与编程竞赛共同成长，并转型成为一名编程竞赛组织者，她创办的编程俱乐部联盟（Programming Club League, PCL）是她所在城市最受欢迎的运动。

Sphinny 的城市中有 $N$ 个公交车站和 $M$ 条快速公交线路。每条线路双向连接两个不同的公交车站，称为它们的端点。由于 PCL 的普及，每条公交线路的司机都只为一个俱乐部加油。

Sphinny 需要在公交车站 $P_j$ 为第 $j$ 场竞赛领取竞赛材料，然后竞赛将在公交车站 $C_j$ 举行。她只能使用给定的公交线路在它们之间往返。形式上，Sphinny 从 $P_j$ 到 $C_j$ 的路径是一系列公交线路，使得每两条连续的线路都有一个公共端点。此外，路径中的第一条线路以 $P_j$ 为端点，最后一条线路以 $C_j$ 为端点。注意，同一条公交线路可以在路径中多次使用。如果 Sphinny 从 $P_j$ 到 $C_j$ 的路径包含一条或多条司机为俱乐部 $c$ 加油的公交线路，则俱乐部 $c$ 将参加该竞赛。否则，俱乐部 $c$ 将不会参加该竞赛。出于组织原因，Sphinny 需要每场竞赛参加的俱乐部数量为奇数。

给定 Sphinny 城市的公交线路布局和竞赛详情，找出有多少场竞赛存在一条路径，使得 Sphinny 可以确保参加该竞赛的俱乐部数量为奇数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含三个整数 $N$、$M$ 和 $Q$：分别表示公交车站的数量、公交线路的数量和竞赛的数量。

接下来 $M$ 行，每行代表一条不同的公交线路。第 $i$ 行包含三个整数 $U_i$、$V_i$ 和 $K_i$，表示第 $i$ 条公交线路连接公交车站 $U_i$ 和 $V_i$，其司机为俱乐部 $K_i$ 加油。

最后 $Q$ 行，每行代表一场竞赛。第 $j$ 行包含两个整数 $P_j$ 和 $C_j$，表示第 $j$ 场竞赛的材料需要在公交车站 $P_j$ 领取，且竞赛需要在公交车站 $C_j$ 举行。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Sphinny 可以找到确保奇数个俱乐部参加的路径的竞赛数量。

数据范围

$1 \le T \le 100$ $1 \le U_i \le N$ $1 \le V_i \le N$ $U_i \neq V_i$ $(U_i, V_i) \neq (U_j, V_j)$ 且 $(U_i, V_i) \neq (V_j, U_j)$，对于所有 $i \neq j$（没有两条公交线路具有相同的端点对）。 $1 \le P_j \le N$ $1 \le C_j \le N$ $P_j \neq C_j$

样例

输入格式 1

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

输出格式 1

Case #1: 1
Case #2: 1

说明

样例 1 的情况如上图所示。在前两场竞赛中，无论选择什么路径，两个俱乐部（绿色和蓝色）都必须参加。对于最后一场竞赛，通过经过公交车站 $1, 2, 4, 5$ 的路径，可以只让绿色俱乐部参加。

对于样例 2，第一场竞赛是不可能的，因为没有从公交车站 $1$ 到公交车站 $2$ 的路径。对于第二场竞赛，存在一条包含唯一一条从公交车站 $1$ 到公交车站 $3$ 的公交线路的路径，因此产生的竞赛恰好有 $1$ 个俱乐部参加，这是一个可接受的奇数。

附加样例 - 测试集 2

以下附加样例符合测试集 2 的限制。它不会在提交的解决方案中运行。

输入格式 2

1
4 5 2
1 2 3
1 3 3
3 4 7
2 3 3
2 4 6
1 2
1 4

输出格式 2

Case #1: 2

说明

该附加样例的情况如上图所示。在这种情况下，两场竞赛都可以以奇数个俱乐部完成。图中展示了实现这一点的示例路径。