산악 투어 (라지)

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

산에는 캠프가 $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이다.