산악 투어 (라지)

문제

에베레스트산 정상에 올라와 있고, 산 위에 있는 등산로를 전부 즐기고 싶다. 그런데 경험상 에베레스트산을 혼자 돌아다니는 것은 위험하다. 어두워지면 길을 잃기 때문이다. 그래서 미리 정해진 시각에 가이드와 함께 출발하는 투어만 이용하려고 한다.

산에는 캠프가 $C$ 개 있고 1번부터 $C$ 번까지 번호가 붙어 있다. 등산 투어는 $2C$ 개 있고 1번부터 $2C$ 번까지 번호가 붙어 있으며, 모두 한 방향으로만 운행한다. 각 투어는 한 캠프에서 출발해 다른 캠프에서 끝나고, 중간에 다른 캠프를 지나지 않는다. 에베레스트산은 인적이 드물어 장사가 잘되지 않는다. 각 캠프에서 출발하는 투어는 정확히 2개이고, 각 캠프에 도착하는 투어도 정확히 2개이다.

모든 투어는 매일 운행한다. 1번과 2번 투어는 1번 캠프에서 출발하고, 3번과 4번 투어는 2번 캠프에서 출발한다. 일반적으로 $2i - 1$ 번 투어와 $2i$ 번 투어가 $i$ 번 캠프에서 출발한다. $i$ 번 투어는 $E_i$ 번 캠프에서 끝나고, 매일 $L_i$ 시에 출발하며, 소요 시간은 정확히 $D_i$ 시간이다.

지금은 0시이고, 하루의 시각은 0시부터 23시까지이다. 현재 1번 캠프에 있고, 투어를 전부 정확히 한 번씩 이용한 다음 1번 캠프로 돌아오려고 한다. 투어를 타지 않고는 캠프 사이를 이동할 수 없다. 캠프에서는 0시간을 포함해 원하는 만큼 기다릴 수 있지만, 투어는 출발하는 시각에만 탈 수 있다.

일정표를 살펴보니 목표를 이루는 방법이 분명히 있다. 이제 최대한 빨리 끝내고 싶다. 경로를 가장 좋게 짰을 때 투어를 모두 마치는 데 몇 시간이 걸리는지 구하라.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 캠프의 개수 $C$ 가 주어진다. 이어서 $2C$ 개의 줄이 주어진다. 그중 1부터 세어 $i$ 번째 줄은 $\lfloor (i+1)/2 \rfloor$ 번 캠프에서 출발하는 투어 하나를 나타내고, 세 정수 $E_i$ , $L_i$ , $D_i$ 로 이루어진다. 이 형식 덕분에 각 캠프에서 출발하는 투어는 정확히 2개가 된다.

제한

$1 \le T \le 100$
$2 \le C \le 1000$
$1 \le E_i \le C$
모든 $i$ 에 대해 $E_i \ne \lceil i/2 \rceil$ , 즉 출발 캠프와 도착 캠프가 같은 투어는 없다
모든 캠프 $v$ 에 대해 $|\{ j : E_j = v \}| = 2$ , 즉 각 캠프에 도착하는 투어는 정확히 2개이다
$0 \le L_i \le 23$
$1 \le D_i \le 1000$
1번 캠프에서 출발해 투어를 전부 정확히 한 번씩 이용하고 1번 캠프로 돌아오는 경로가 적어도 하나 있다

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 목표를 이루는 데 걸리는 최소 시간이다.

힌트

첫 번째 테스트 케이스의 최적 계획은 다음과 같다.

1번 캠프에서 한 시간 기다려 1시가 되게 한다.
1시에 1번 캠프를 떠나 5시간짜리 투어를 타고 6시에 2번 캠프에 도착한다.
6시에 곧바로 2번 캠프를 떠나 3시간짜리 투어를 타고 9시에 1번 캠프에 도착한다.
1번 캠프에서 15시간 기다려 다음 날 0시가 되게 한다.
0시에 1번 캠프를 떠나 3시간짜리 투어를 타고 3시에 2번 캠프에 도착한다.
2번 캠프에서 한 시간 기다려 4시가 되게 한다.
4시에 2번 캠프를 떠나 4시간짜리 투어를 타고 8시에 1번 캠프에 도착한다.

이렇게 하면 1일 8시간, 즉 32시간이 걸린다. 다른 계획은 모두 이보다 오래 걸린다.

두 번째 테스트 케이스에서는 투어가 전부 같은 시각에 출발하고 소요 시간도 같다. 투어 하나를 마치면 곧바로 다음 투어를 탈 수 있다. 입력에 나온 순서대로 투어에 1번부터 8번까지 번호를 붙이면, 최적 계획 중 하나는 1, 5, 4, 7, 6, 2, 3, 8이다.