대회 피자 자르기

2007년 가을에는 "프로그래밍 대회 프로그래밍 대회"가 열렸다. 참가자가 풀어야 하는 문제가 프로그래밍 대회를 운영하는 문제였다. 대회 운영에서 가장 중요한 것은 피자다.

피자는 반지름이 1인 원이고, 그 위에 콩고기 조각이 올려져 있다. 아직 자르지 않은 이 피자를 여러 조각으로 나눠야 한다. 지켜야 할 조건은 두 가지다. 모든 조각의 크기가 같아야 하고, 각 조각에 올라간 콩고기 개수도 모두 같아야 한다.

자르는 방법에도 제약이 있다. 칼질은 원의 중심에서 원둘레까지 이어지는 직선을 따라서만 할 수 있다. 또 콩고기를 지나가도록 자를 수는 없고, 콩고기는 언제나 자른 선의 한쪽에 온전히 놓여야 한다.

콩고기의 위치가 주어질 때, 두 조건을 모두 만족하면서 피자를 나눌 수 있는 조각 수의 최댓값을 구하는 프로그램을 작성한다. 자르지 않고 한 조각으로 두는 것은 언제나 가능하므로 답은 항상 존재한다.

첫 줄에 데이터 집합의 개수 $K$가 주어진다 ($1 \le K \le 20$). 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 피자 위 콩고기의 개수 $N$이 주어진다 ($1 \le N \le 200$). 다음 $N$개의 줄에는 콩고기의 위치가 한 줄에 하나씩 주어진다. 위치는 피자 중심을 기준으로 한 극좌표이고, 한 줄에 두 실수 $\alpha$와 $r$가 공백으로 구분되어 주어진다. $\alpha$는 양의 $x$축에서 중심과 콩고기를 잇는 선분까지 반시계 방향으로 잰 각이며 $0 \le \alpha < 2\pi$이다. $r$는 중심에서 콩고기까지의 거리이며 $0 < r \le 1$이다. 피자의 반지름은 1이다. 두 값 모두 소수점 아래 최대 6자리까지 주어진다. 콩고기는 점으로 보며, 같은 자리에 놓인 콩고기는 없다. 각도가 같고 중심에서의 거리만 다른 콩고기는 있을 수 있다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 데이터 집합의 번호이고 1부터 센다. 다음 줄에는 나눌 수 있는 조각 수의 최댓값을 $y$라 할 때 y slices를 출력한다. 최댓값이 1일 때도 1 slices로 출력한다. 각 데이터 집합의 출력 뒤에는 빈 줄을 하나 출력한다.