로빈트론

2240년 대전쟁이 한창이던 무렵, 로빈슨 가족은 더 평화롭고 조용한 곳을 찾아 인류 제국을 떠나기로 결심한다. 이들은 이미 목적지 행성을 정해 두었고, 최대한 빨리 그곳에 도착하고 싶어 한다. 그러나 우주 비행이 가능한 모든 탈것이 전쟁에 동원된 탓에, 로빈슨 가족은 평범한 우주 비행으로는 다른 행성으로 탈출할 방법이 없다. 그래서 가장인 조 로빈슨은 오직 중력의 힘만으로 한 행성의 표면에서 다른 행성의 표면으로 이동하는 탈것, 로빈트론(Robintron) 을 만들어 냈다.

로빈트론을 행성 표면에 붙잡아 두는 것은 그 행성의 중력이다. 이 중력은 행성의 질량이 만들어 내는 중력 우물(gravity well), 즉 행성 중심을 중심으로 하는 반지름 $r$ 의 원형 영역까지 미친다. 중력 우물은 행성 도약(planet hopping) 을 통해 행성을 떠나는 데에도 쓸 수 있다. 행성 도약은 로빈트론이 어떤 행성의 표면에 있으면서 다른 행성의 중력 우물 안에 들어왔을 때 수행할 수 있다. 로빈트론은 그 다른 행성의 중력 우물을 이용해 우주로 탈출할 만큼의 운동량을 얻어 그 행성의 표면에 착륙한다. 한 행성을 떠나 다른 행성에 착륙하는 데에는 의미 있는 시간이 걸리지 않는다.

행성 도약에는 제약이 있다. 도약을 하려면 로빈트론은 지금 있는 행성이 아닌 다른 행성의 중력 우물 안에 있어야 한다. 모든 행성은 완벽한 원 궤도로 중심 별 주위를 돌기 때문에 각자의 회전 속도에 따라 위치가 끊임없이 바뀌며, 따라서 특정 행성의 중력 우물이 로빈트론이 닿는 범위 안에 들어오기까지 시간이 걸릴 수 있다. 또한 로빈트론이 어떤 행성의 중력 우물 안으로 들어가 그 행성으로 도약하는 순간, 로빈트론은 그 행성과 함께 별 주위를 돌게 된다. 그 결과 또 다른 행성의 중력 우물은 영영 닿는 범위 안에 들어오지 않을 수도 있다.

항성계의 행성 목록과 출발 위치, 목적지가 주어질 때, 로빈트론이 가능한 가장 빠른 경로로 목적지까지 이동하는 데 며칠이 걸리는지를 구하는 프로그램을 작성하라. 일수는 올림(ceiling) 함수로 올림한다 (예: $\lceil 2.3 \rceil = 3$).

대부분의 항성계에서 모든 행성은 별을 중심으로 하나의 원반 위에 놓이므로 2차원만 고려하면 된다. 또한 각 행성은 공간상의 한 점으로 취급하며, 로빈트론의 좌표는 자신이 있는 행성의 좌표와 같다.

첫째 줄에 테스트 케이스의 개수 $n$ 이 정수로 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

항성계에 있는 행성의 수 $m$ ($0 < m < 1000$) 이 양의 정수로 한 줄에 주어진다. 별은 항상 $[0, 0]$ 에 있으며 이 수에 포함되지 않는다.
이어서 행성마다 한 줄씩, 공백으로 구분된 네 개의 수가 주어진다. $x$ ($-10^{10} \le x \le 10^{10}$) 와 $y$ ($-10^{10} \le y \le 10^{10}$) 는 여정이 시작될 때 별을 기준으로 한 행성의 $x$, $y$ 좌표, $r$ ($0 < r \le 10^5$) 은 행성의 중력 우물 반지름, $s$ ($0 \le s \le 2\pi$) 는 행성이 별 주위를 반시계 방향으로 도는 각속도(하루당 라디안)이다.

로빈트론은 항상 첫 번째로 주어진 행성에서 출발하며, 목적지는 항상 마지막으로 주어진 행성이고 출발 위치에서 반드시 도달할 수 있다. $[0, 0]$ 에 있는 별은 너무 뜨거워서 행성 도약에 사용할 수 없다.

문제

입력

출력