등산하는 사슴

문제

사슴 허버트는 하이킹을 떠난다. 가장 좋아하는 원형 등산로를 시계 방향으로 정확히 한 바퀴 도는 것이 목표이고, 출발점은 0도 지점이다. 허버트는 속력을 완벽하게 조절한다. 어느 순간에나 속력을 0 이상의 아무 실숫값으로 정할 수 있고, 정수일 필요는 없다. 원하면 언제든 즉시 속력을 바꾼다. 출발점으로 다시 돌아오는 순간 하이킹이 끝난다.

같은 등산로를 사람들도 이용한다. 등산객도 모두 시계 방향으로 걷는다. 등산객은 저마다 출발 위치가 있고 저마다 일정한 속력으로 걸으며, 등산로를 영원히 돌고 또 돈다.

허버트는 겁이 많아서 사람을 무서워한다. 허버트와 등산객이 같은 시각에 정확히 같은 지점에 있으면 마주침이 한 번 일어난다. 허버트와 등산객은 모두 원 둘레 위의 점으로 본다.

같은 등산객과 여러 번 마주칠 수 있고, 그 마주침은 각각 따로 센다.
같은 순간에 여러 등산객과 마주치면 등산객 수만큼 따로 센다.
하이킹이 끝나는 바로 그 순간에 일어난 마주침도 센다.
어떤 등산객과 마주친 뒤 그 등산객과 속력을 정확히 맞춰 따라가면 마주침이 무한히 많아진다. 허버트는 절대 그렇게 하지 않는다.
마주침은 등산객의 행동을 바꾸지 않고, 등산객끼리 마주쳐도 아무 일도 일어나지 않는다.

허버트는 모든 등산객의 출발 위치와 속력을 안다. 허버트가 겪는 마주침 횟수의 최솟값을 구하라.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스의 첫째 줄에는 정수 $N$ 이 주어지고, 이어지는 $N$ 개의 줄에는 등산로의 같은 지점에서 출발하는 등산객 그룹이 한 줄에 하나씩 주어진다. 각 줄에는 세 정수 $D_i$ , $H_i$ , $M_i$ 가 공백으로 구분되어 주어진다. $D_i$ 는 그룹의 출발 위치이며, 사슴의 출발점에서 시계 방향으로 등산로 전체의 $D_i/360$ 만큼 떨어진 지점을 뜻한다. $H_i$ 는 그룹에 속한 등산객 수, $M_i$ 는 그룹에서 가장 빠른 등산객이 한 바퀴를 도는 데 걸리는 시간(분)이다. 그룹의 나머지 등산객은 한 바퀴를 도는 데 각각 $M_i+1$ , $M_i+2$ , ..., $M_i+H_i-1$ 분이 걸린다. 예를 들어 180 3 4라는 줄은 사슴의 출발점에서 등산로를 절반 돈 지점에서 등산객 세 명이 출발하고, 이들이 한 바퀴를 도는 데 각각 4분, 5분, 6분이 걸린다는 뜻이다.

허버트는 항상 위치 0에서 출발하고, 등산객 그룹은 위치 0에서 출발하지 않는다. 여러 그룹이 같은 지점에서 출발하기도 하지만, 출발 지점과 속력이 둘 다 같은 등산객 두 명은 없다.

제한

$1 \le T \le 100$
$1 \le N \le 1000$
$1 \le D_i \le 359$
$1 \le H_i$
$1 \le M_i \le 10^9$ (이 조건은 각 그룹에서 가장 빠른 등산객의 소요 시간만 제한한다. 같은 그룹의 느린 등산객은 더 오래 걸린다.)
한 테스트 케이스에 등장하는 등산객 수의 합은 10 이하이다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 사슴이 겪는 마주침 횟수의 최솟값이다.

힌트

첫 번째 예제의 테스트 케이스 1에서는 등산객이 모두 같은 속력으로 움직인다. 허버트가 그들과 똑같은 속력으로 움직이면 아무와도 마주치지 않는다.

테스트 케이스 2에서는 두 번째 등산객이 첫 번째 등산객보다 훨씬 빠르다. 첫 번째 등산객을 추월하지 않을 만큼 느리게 가면 빠른 두 번째 등산객과 여러 번 마주친다. 최적인 방법 하나는 두 번째 등산객과 똑같은 속력으로 가는 것이다. 이러면 첫 번째 등산객과 한 번 마주치고 두 번째 등산객과는 한 번도 마주치지 않는다.

테스트 케이스 3에서는 두 등산객이 같은 지점에서 출발하고 한 명이 다른 한 명보다 두 배 빠르다. 최적인 방법 하나는 느린 등산객을 추월하지 않고 바로 뒤까지 따라붙은 다음, 그 등산객이 사슴의 출발 지점을 지날 때까지 뒤를 따라가다가, 빠른 등산객이 따라잡기 전에 남은 거리를 빠르게 끝내는 것이다.