산악 투어 (작은 입력)

문제

에베레스트 정상에 올라와 있고, 그곳에 있는 하이킹 투어를 전부 즐기려고 한다. 혼자 돌아다니면 해가 진 뒤에 길을 잃기 쉬우니, 정해진 시각에 출발하는 가이드 투어로만 이동한다.

산에는 캠프가 $C$ 개 있고 1번부터 $C$ 번까지 번호가 붙어 있다. 일방통행 하이킹 투어는 $2 \times C$ 개이고 1번부터 $2 \times C$ 번까지 번호가 붙어 있다. 각 투어는 한 캠프에서 출발해 다른 캠프에서 끝나며, 중간에 다른 캠프를 지나지 않는다. 에베레스트는 사람이 적어 장사가 한산하다. 캠프마다 출발하는 투어가 정확히 2개, 도착하는 투어가 정확히 2개다.

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

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

목표를 달성하는 경로는 반드시 존재하고, 그중 가장 빠른 경로를 찾고 싶다. 경로를 최적으로 짜면 모든 투어를 마치는 데 몇 시간이 걸리는가?

입력

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

제한

$1 \le T \le 100$
$2 \le C \le 15$
$1 \le E_i \le C$
모든 $i$ 에 대해 $E_i \ne \lceil i / 2 \rceil$ . 즉 출발 캠프와 도착 캠프가 같은 투어는 없다
모든 캠프 $i$ 에 대해 $|\{ j : E_j = i \}| = 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시에 1번 캠프를 떠나 5시간짜리 투어를 타고 6시에 2번 캠프에 도착한다.
6시에 곧바로 2번 캠프를 떠나 3시간짜리 투어를 타고 9시에 1번 캠프에 도착한다.
1번 캠프에서 15시간 기다려 다음 날 0시가 된다.
0시에 1번 캠프를 떠나 3시간짜리 투어를 타고 3시에 2번 캠프에 도착한다.
2번 캠프에서 1시간 기다려 4시가 된다.
4시에 2번 캠프를 떠나 4시간짜리 투어를 타고 8시에 1번 캠프에 도착한다.

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

두 번째 테스트 케이스에서는 모든 투어의 출발 시각과 운행 시간이 같다. 투어 하나를 마치면 다음 투어를 곧바로 탈 수 있다. 그 테스트 케이스에 나온 순서대로 투어에 1번부터 8번까지 번호를 붙이면, 최적 계획 하나는 1, 5, 4, 7, 6, 2, 3, 8이다.