강아지 산책

당신은 래브라도 한 마리를 키우고 있다. 이 개는 충분히 운동하지 않으면 게을러지고 살이 찌기 때문에, 당신은 종종 동네 공원으로 산책을 데려간다.

당신 자신은 이미 충분히 운동하고 있고 개를 쫓아 뛰어다니고 싶지 않아서, 아주 긴 밧줄을 사서 한쪽 끝을 개에게 묶었다. 이 밧줄의 길이는 무한하다고 가정한다. 당신은 앉기 좋은 곳에 자리를 잡고 밧줄의 다른 한쪽 끝을 잡은 채, 개가 자유롭게 뛰어다니게 한다. 개가 공원을 돌아다니는 동안 밧줄은 공원 한가운데에 서 있는 깃대에 감길 수 있다. 당신은 이를 허용하지만, 밧줄이 당신이 앉아 있는 곳을 지나갈 때에는 얽히지 않도록 그 위를 뛰어넘는다.

개가 차례대로 도착하는 점들이 주어질 때, 산책이 끝난 뒤 밧줄이 깃대에 완전히 몇 번 감겼는지 구해야 한다. 답은 정수로 내림한다. 개는 항상 다음 점까지 최단 경로로 이동한다. 이 경로가 정확히 깃대를 지나가면, 개는 깃대를 반시계 방향으로 돌아간다.

공원은 -10^9 <= x, y <= 10^9 범위의 좌표평면으로 나타낸다. 깃대는 (0, 0)에 있다.

첫째 줄에는 테스트 케이스의 수 n (0 < n <= 10000)이 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫 줄에는 개의 산책을 이루는 점의 수 m (0 < m <= 1000)이 주어진다.
• 이어지는 m개의 줄에는 개가 i번째로 달려갈 점의 좌표인 두 정수 x_i, y_i (-10^9 <= x_i, y_i <= 10^9, (x_i, y_i) != (0, 0))가 주어진다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 이 정수는 당신이 (x_1, y_1)에 앉아 있고, 개가 (x_1, y_1) -> (x_2, y_2) -> ... -> (x_m, y_m) 순서로 이동한 뒤 밧줄이 깃대에 완전히 감긴 횟수이다.