Graduation Requirements (Small)

Students at Awesome Programmer University perform a few traditional stunts before they graduate. One of them is driving around a traffic circle backwards. That is reckless enough for most people, so you set yourself a harder goal: going backwards around the circle several times without stopping.

The traffic circle has $N$ intersections spaced evenly around it. A car enters the circle at one intersection, then every second it moves to the next intersection counter-clockwise, until it reaches its destination and leaves.

You watched cars enter and leave the circle for $X$ seconds. For every car you recorded the time it entered, the intersection it entered at, and the intersection it left at. All cars move counter-clockwise at 1 intersection per second. Every car you watched left the circle before it came back to the intersection it entered at. The circle has several lanes, so more than one car can sit at the same intersection at the same time.

If you had planned it perfectly, how long could you have driven clockwise inside the circle during that time? You must enter at an integer time of at least 0, you must leave at a time of at most $X$, and once you leave you cannot come back. Inside the circle you move clockwise at 1 intersection per second. You must never touch another car and never cross one head on. In particular, you cannot leave the circle at an intersection where another car is entering at the same moment, and you cannot enter the circle at an intersection where another car is leaving at the same moment. You choose when and where to enter and leave.

The first line contains the number of test cases $T$. The test cases follow.

The first line of a test case contains the number of observed cars $C$. The second line contains two integers $X$ and $N$, the length of the observation in seconds and the number of intersections. The next $C$ lines each contain three integers $s_i$, $e_i$ and $t_i$, the intersection where the car entered, the intersection where it left, and the time it entered. Intersections are numbered 1 to $N$ counter-clockwise, so intersection 2 is the next intersection counter-clockwise from intersection 1.

Limits

• $1 \le T \le 100$
• $3 \le N \le 10$
• $1 \le X \le 10$
• $0 \le C \le 10$
• $1 \le s_i, e_i \le N$
• $s_i \ne e_i$
• $0 \le t_i$
• Every observed car leaves the circle at time $X$ or earlier.

For each test case, print one line of the form Case #x: y, where x is the test case number starting from 1 and y is the largest number of seconds you can drive clockwise inside the circle. y is 0 both when you cannot enter the circle at all and when you can enter it but cannot move even one intersection.

You must enter the circle at an integer number of seconds, so you also arrive at every intersection at an integer time.

The first test case has one car, moving as in the picture above. Several routes let you drive backwards for one second. You can enter at intersection 1 at time 1 and drive to intersection 4. At time 0 the other car sits at intersection 1, so you cannot enter then, and you have to stop at intersection 4, because going on to intersection 3 would cross the other car while it moves from 3 to 4. Another option is to enter at intersection 4 at time 0, drive to intersection 3, and leave.

In the second test case you drive for two seconds by entering at intersection 5 at time 1 and driving backwards to intersection 3. In the third test case you cannot enter at all, because a car sits at every intersection at every whole second. The fourth test case has no cars, so you enter anywhere at time 0 and keep going until time 6. In the fifth test case you can enter, but with only three intersections you always hit the other car as soon as you move.

Driving against traffic on a real traffic circle is dangerous. Do not try it.