Noah 拥有一棵包含 $n$ 个顶点的无根树，顶点编号从 $1$ 到 $n$。每天早晨，Noah 都会选择两个顶点 $u$ 和 $v$ 来获取日光的影响，随后这种影响会沿着边传播，但如果影响经过的边数超过 $w$，它就会消失。

你的任务是计算每天受到日光影响的顶点数量。此外，输入数据将被加密以确保你的解决方案是在线处理的。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 接下来描述所有测试用例。对于每个测试用例： 第一行包含两个整数 $n$ 和 $m$。 接下来的 $(n - 1)$ 行，每行包含两个整数 $u$ 和 $v$，表示顶点 $u$ 和顶点 $v$ 之间的一条边。 令 $lastans$ 为每天之前的最后一次答案。在每个测试用例的第一天开始时，$lastans$ 初始化为 $0$。 接下来的 $m$ 行，每行包含三个整数 $u', v'$ 和 $w'$，满足 $u = ((u' + lastans) \pmod n) + 1$，$v = ((v' + lastans) \pmod n) + 1$，$w = (w' + lastans) \pmod n$，这意味着在某一天，Noah 会选择顶点 $u$ 和 $v$ 来获取影响，如果影响经过的边数超过 $w$，它就会消失。

$1 \le T \le 100$，$1 \le n, m \le 10^5$，$1 \le u, v, u', v' \le n$，$0 \le w' < n$。 保证不超过 $10$ 个测试用例不满足 $n, m \le 10^3$，且标准输入文件的大小不超过 $32$ MiB。

输出格式

对于每一天，输出一行答案。 保证标准输出文件的大小不超过 $7$ MiB。

样例

输入 1

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

输出 1

2
4
5
5
5

说明

解密后的信息如下：

• 第 1 天：$u = 1, v = 2, w = 0$；
• 第 2 天：$u = 1, v = 2, w = 1$；
• 第 3 天：$u = 1, v = 2, w = 2$；
• 第 4 天：$u = 1, v = 2, w = 3$；
• 第 5 天：$u = 1, v = 2, w = 4$。