등산하는 사슴 (큰 입력)

사슴 허버트는 좋아하는 원형 등산로를 시계 방향으로 한 바퀴 돈다. 출발 지점은 0도이고, 출발 지점으로 다시 돌아오면 산행이 끝난다. 허버트는 속도를 완벽하게 조절한다. 어느 순간에나 0 이상인 아무 실숫값이나 속도로 삼을 수 있고, 정수가 아니어도 되며, 원할 때 즉시 속도를 바꿀 수 있다.

이 등산로는 사람도 쓴다. 사람도 시계 방향으로 걷고, 각자 정해진 출발 지점에서 자기 속도로 일정하게 움직이며, 등산로를 영원히 돈다.

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

허버트는 같은 등산객과 여러 번 따로 마주칠 수 있다. 같은 순간에 여러 등산객과 마주치면 각각 다른 마주침으로 센다. 산행이 끝나는 바로 그 순간에 일어난 마주침도 센다. 어떤 등산객과 마주친 뒤 속도를 그 등산객과 똑같이 맞춰 따라가면 마주침이 무한히 많아지므로, 허버트는 절대 그렇게 하지 않는다. 마주쳐도 등산객이 걷는 방식은 달라지지 않고, 등산객끼리 마주쳐도 아무 일도 일어나지 않는다.

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

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 정수 $N$이 적힌 줄로 시작하고, 이어서 $N$개의 줄이 주어진다. 각 줄은 등산로의 같은 지점에서 출발하는 등산객 그룹 하나를 나타낸다. 이 중 $i$번째 줄에는 세 정수가 공백으로 구분되어 주어진다. 출발 위치 $D_i$는 사슴의 출발 지점에서 시계 방향으로 $D_i/360$ 바퀴만큼 떨어진 지점을 뜻하고, $H_i$는 그룹에 속한 등산객 수, $M_i$는 그룹에서 가장 빠른 등산객이 한 바퀴를 도는 데 걸리는 시간(분)이다. 같은 그룹의 나머지 등산객은 한 바퀴에 각각 $M_i+1, M_i+2, \dots, M_i+H_i-1$분이 걸린다.

예를 들어 180 3 4이라는 줄은 등산객 세 명이 사슴의 출발 지점에서 반 바퀴 떨어진 곳에서 출발하고, 한 바퀴를 도는 데 각각 4분, 5분, 6분이 걸린다는 뜻이다.

허버트는 항상 위치 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$. 이 값은 각 그룹에서 가장 빠른 등산객만 제한하므로, 같은 그룹의 느린 등산객은 더 오래 걸린다.
• 한 테스트 케이스에 나오는 등산객 수의 합은 $500000$ 이하이다.

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

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

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

세 번째 테스트 케이스에서는 두 등산객이 같은 지점에서 출발하지만 한 명이 다른 한 명보다 두 배 빠르다. 최적인 방법 하나는 느린 등산객을 앞지르지 않으면서 곧바로 바짝 따라붙어 있다가, 그 등산객이 사슴의 출발 지점을 지난 뒤 빠른 등산객이 사슴을 따라잡기 전에 서둘러 한 바퀴를 마치는 것이다.