Inkopolis 是 Inklings 居住的城市，它可以被看作是一个无向连通图，恰好有 $N$ 个顶点和 $N$ 条边。保证图中没有重边或自环。Inklings 可以喷洒一种特殊的彩色墨水来装饰他们居住的道路。Inklings 生性多变，所以他们经常改变道路的颜色来庆祝即将到来的 Splatfest。

Splatfest 持续 $M$ 天，每天 Inklings 会在恰好一条道路上喷洒墨水，这条道路原有的颜色会被新的墨水颜色覆盖。在每一天结束时，他们想知道 Inkopolis 中有多少个不同的颜色区域。一个颜色区域是指一组颜色相同且连通的道路，更明确地说，如果两条道路颜色相同且共享一个公共顶点，则它们处于同一个颜色区域中。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含两个整数 $N$ 和 $M$，其中 $N$ 是 Inkopolis 中的顶点数和道路数，$M$ 是 Splatfest 持续的天数。

接下来的 $N$ 行描述了顶点之间的道路。每行包含 3 个整数 $x, y, c$，表示第 $x$ 个顶点和第 $y$ 个顶点之间有一条颜色为 $c$ 的道路。

接下来的 $M$ 行描述了每天的操作。每行包含 3 个整数 $x, y, c$，表示 Inklings 在第 $x$ 个顶点和第 $y$ 个顶点之间的道路上喷洒颜色为 $c$ 的墨水，保证该道路存在。

输出格式

对于每个测试用例，首先输出一行 “Case #x:”，其中 $x$ 是测试用例编号（从 1 开始）。

接下来的 $M$ 行，每行包含一个整数，表示每天结束后 Inkopolis 中颜色区域的数量。

数据范围

• $1 \le T \le 100$
• $3 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le x, y, c \le N$
• $\sum N, \sum M \le 10^6$

样例

样例输入 1

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

样例输出 1

Case #1:
4
3
3
Case #2:
2
4
2
2