在 Awesome Programmer University 毕业之前，学生们通常需要完成一些“毕业要求”。其中一项就是逆向绕行交通环岛。对大多数人来说，这已经足够疯狂了，但作为一项额外的挑战，你想要看看自己是否能在不停车的情况下，逆向绕行交通环岛多次。

交通环岛由 $N$ 个均匀分布在圆周上的交叉路口组成。汽车通常会在一个交叉路口进入环岛，然后每秒移动到下一个逆时针方向的交叉路口，直到最终到达目的地并离开。

你已经观察了汽车进入和离开交通环岛 $X$ 秒。对于每一辆车，你记录了它进入环岛的时间，以及它进入和离开的交叉路口。所有汽车都以每秒 1 个交叉路口的速率逆时针移动。你观察到的每辆车在回到它进入的交叉路口之前就已经离开了环岛。交通环岛有多条车道，因此多辆车可以在同一时间占据同一位置。

如果你计划得当，在这段时间内你最多能顺时针驾驶多久？你必须在某个整数时间 $\ge 0$ 进入环岛，在时间 $\le X$ 时离开，且一旦离开，就不允许再回来。在环岛内时，你必须以每秒 1 个交叉路口的速率顺时针行驶。为了安全起见（好吧，在交通环岛上逆向行驶能有多安全呢），你绝对不能触碰或超过其他车辆。特别地，你不能在另一辆车正要进入的交叉路口离开环岛，也不能在另一辆车正要离开的交叉路口进入环岛。你可以选择进入和离开环岛的时间与地点。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行描述了你观察到的汽车数量 $C$。第二行包含两个整数 $X$ 和 $N$ —— 你观察环岛的时间（以秒为单位）以及环岛上的交叉路口数量。接下来的 $C$ 行描述了你观察到的汽车。每一行包含三个整数 $s_i$、$e_i$ 和 $t_i$ —— 分别表示汽车进入环岛的交叉路口、离开的交叉路口以及进入的时间。交叉路口编号为 1 到 $N$，按逆时针方向排列（即交叉路口 2 是交叉路口 1 逆时针方向的下一个路口）。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是你可以顺时针行驶的最长时间（秒）。注意，如果你根本无法进入环岛，或者虽然能进入但无法行驶哪怕一个交叉路口，结果 $y$ 都可以为 0。

请记住，你必须在整数秒时刻进入环岛 —— 你必须在整数时间进入，因此在到达每个交叉路口时也都是整数时间。

数据范围

时间限制：6 秒。 内存限制：1GB。

$1 \le T \le 100$ $1 \le s_i, e_i \le N$ $s_i \neq e_i$ $0 \le t_i$ 每辆被观察到的汽车都在时间 $X$ 或之前离开环岛。

小数据（测试集 1 - 可见）

$3 \le N \le 10$ $1 \le X \le 10$ $0 \le C \le 10$

大数据（测试集 2 - 隐藏）

$3 \le N \le 10^{10}$ $1 \le X \le 10^{10}$ $0 \le C \le 1000$

样例

输入 1

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

输出 1

Case #1: 1
Case #2: 2
Case #3: 0
Case #4: 6
Case #5: 0

说明

在第一个样例中，有一辆车，行驶路径如图所示。有多种方式可以让我们逆向行驶一秒 —— 例如，我们可以在时间 1 进入交叉路口 1（我们不能在时间 0 进入，因为另一辆车在那里），然后行驶到交叉路口 4（我们不能继续前往交叉路口 3，因为我们会经过那辆正从 3 前往 4 的车）。另一种选择是在时间 0 进入交叉路口 4，然后行驶到交叉路口 3（随后离开）。

在第二个样例中，我们可以通过在时间 1 进入交叉路口 5，并逆向行驶到交叉路口 3，从而行驶两秒。在第三个样例中，我们甚至无法进入环岛 —— 在每个整秒时刻，所有交叉路口都有车。在第四个样例中，没有车，所以我们可以在时间 0 从任意点进入，并绕圈行驶直到时间 6。在第五个样例中，我们可以进入环岛，但由于只有三个交叉路口，如果我们尝试移动到下一个路口，总是会与另一辆车发生碰撞。

注意：在交通环岛上逆向行驶通常不是明智之举，可能会对自己或他人造成伤害。Google（特别是 Google Code Jam）鼓励你不要尝试这样做。