하이킹하는 사슴 (Small1)

사슴 허버트는 원형 산책로를 시계 방향으로 정확히 한 바퀴 돈다. 출발 지점은 0도이고, 다시 출발 지점으로 돌아오는 순간 산책이 끝난다. 허버트는 속도를 완벽하게 조절한다. 속도는 언제나 0 이상의 실수면 되고(정수가 아니어도 된다), 원하는 순간에 즉시 바꾼다.

같은 산책로를 사람 등산객도 시계 방향으로 걷는다. 각 등산객은 자기 출발 지점에서 일정한 속도로 걷고, 멈추지 않고 계속 돈다.

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

• 같은 등산객과 여러 번 마주칠 수 있다.
• 같은 순간에 등산객 여러 명과 만나면 각각을 따로 센다.
• 산책이 끝나는 바로 그 순간에 일어난 마주침도 센다.
• 어떤 등산객과 마주친 뒤 속도를 그 등산객에게 똑같이 맞춰 따라가면 마주침이 무한히 많아진다. 허버트는 절대 그렇게 하지 않는다.
• 마주침은 등산객의 움직임을 바꾸지 않고, 등산객끼리 만나도 아무 일도 일어나지 않는다.

등산객 전원의 출발 지점과 속도를 알 때, 허버트가 겪는 마주침 횟수의 최솟값을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$이 주어지고, 이어지는 $N$개의 줄에 같은 지점에서 출발하는 등산객 그룹이 하나씩 주어진다. $i$번째 줄에는 공백으로 구분된 세 정수 $D_i$, $H_i$, $M_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 100$
• $1 \le D_i \le 359$
• $1 \le H_i$
• $1 \le M_i \le 10^9$ (한 바퀴에 걸리는 시간의 상한은 그룹에서 가장 빠른 등산객에게만 적용된다. 같은 그룹의 느린 등산객은 이보다 오래 걸린다.)
• 한 테스트 케이스에 들어 있는 등산객 수의 합은 500 이하이다.
• 모든 테스트 케이스의 등산객 수를 전부 더한 값은 2000 이하이다.

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

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

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

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