졸업 통과 의례 (스몰)

굉장한 프로그래머 대학교 학생은 졸업 전에 통과 의례를 몇 가지 치른다. 그중 하나가 회전 교차로를 거꾸로 도는 것이다. 보통은 이것만으로도 충분히 무모하지만, 당신은 한 단계 더 어려운 목표를 세웠다. 멈추지 않고 회전 교차로를 거꾸로 여러 바퀴 도는 것이다.

회전 교차로에는 교차점 $N$개가 원을 따라 같은 간격으로 놓여 있다. 자동차는 교차점 하나로 회전 교차로에 들어와 1초마다 반시계 방향으로 다음 교차점으로 이동하고, 목적지에 닿으면 빠져나간다.

당신은 $X$초 동안 자동차가 회전 교차로에 들어오고 나가는 모습을 지켜봤다. 자동차마다 들어온 시각, 들어온 교차점, 나간 교차점을 기록했다. 모든 자동차는 1초에 교차점 하나씩 반시계 방향으로 이동한다. 당신이 지켜본 자동차는 모두 들어온 교차점으로 되돌아오기 전에 회전 교차로를 빠져나갔다. 회전 교차로에는 차로가 여러 개라서 같은 시각에 같은 교차점에 자동차가 여러 대 있어도 된다.

계획을 완벽하게 짰다면 이 시간 동안 시계 방향으로 얼마나 오래 달릴 수 있었을까? 0 이상의 정수 시각에 회전 교차로에 들어가야 하고, $X$ 이하의 시각에 빠져나와야 하며, 한 번 빠져나오면 다시 들어갈 수 없다. 회전 교차로 안에서는 1초에 교차점 하나씩 시계 방향으로 이동한다. 다른 자동차와 절대 닿아서도, 서로 엇갈려 지나가서도 안 된다. 특히 다른 자동차가 같은 순간에 들어오고 있는 교차점에서는 빠져나올 수 없고, 다른 자동차가 같은 순간에 빠져나가고 있는 교차점으로는 들어갈 수 없다. 들어가고 나오는 시각과 위치는 당신이 고른다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫째 줄에는 관찰한 자동차의 수 $C$가 주어진다. 둘째 줄에는 정수 두 개 $X$와 $N$이 주어진다. $X$는 회전 교차로를 지켜본 시간(초)이고, $N$은 교차점의 개수다. 다음 $C$개 줄에는 각각 정수 세 개 $s_i$, $e_i$, $t_i$가 주어진다. 차례로 자동차가 들어온 교차점, 나간 교차점, 들어온 시각이다. 교차점 번호는 반시계 방향으로 1번부터 $N$번까지 붙어 있다. 즉 1번 교차점에서 반시계 방향으로 다음 교차점이 2번이다.

제한

• $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$
• 관찰한 자동차는 모두 시각 $X$ 또는 그 이전에 회전 교차로를 빠져나간다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 회전 교차로 안에서 시계 방향으로 달릴 수 있는 최대 시간(초)이다. 회전 교차로에 아예 들어갈 수 없을 때와, 들어갈 수는 있지만 교차점 하나만큼도 이동할 수 없을 때 모두 y는 0이다.

회전 교차로에 들어가는 시각은 정수여야 하고, 따라서 모든 교차점에 정수 시각에 도착한다.

첫째 테스트 케이스에는 자동차가 한 대 있고, 문제의 그림처럼 움직인다. 1초 동안 거꾸로 달리는 방법은 여러 가지다. 예를 들어 시각 1에 1번 교차점으로 들어가서 4번 교차점까지 갈 수 있다. 시각 0에는 다른 자동차가 1번에 있어서 들어갈 수 없고, 3번까지 더 가면 3번에서 4번으로 이동하는 자동차와 엇갈리므로 4번에서 멈춰야 한다. 시각 0에 4번 교차점으로 들어가서 3번까지 간 다음 빠져나오는 방법도 있다.

둘째 테스트 케이스에서는 시각 1에 5번 교차점으로 들어가 거꾸로 3번 교차점까지 가면 2초 동안 달린다. 셋째 테스트 케이스에서는 매 정수 시각마다 모든 교차점에 자동차가 있어서 아예 들어갈 수 없다. 넷째 테스트 케이스에는 자동차가 없으므로 시각 0에 아무 데나 들어가 시각 6까지 계속 돌면 된다. 다섯째 테스트 케이스에서는 들어갈 수는 있지만 교차점이 세 개뿐이라 한 칸이라도 움직이면 반드시 다른 자동차와 부딪힌다.

실제 회전 교차로를 역주행하는 것은 위험하다. 따라 하지 않기를 권한다.