행성 파괴

다스 베이더가 취미인 행성 파괴로 돌아왔다. 정확히는 행성에 사는 주민을 없애는 일이다. 반란군 지도부가 와투인이라는 행성에 모였다는 사실을 알아낸 베이더는 위협을 서둘러 없애려 한다. 제국은 지금 불황이 심해서 남은 데스 스타가 없다. 그래서 베이더는 치명적인 바이러스가 담긴 용기를 행성 표면에 여러 개 떨어뜨리기로 했다.

문제는 2차원으로 단순화한다. 와투인은 $(0, 0)$을 중심으로 하는 반지름 $R$의 원이다. 제국 우주선 $K$대가 동시에 로켓을 한 발씩 $(0, 0)$ 방향으로 발사한다. 로켓은 직선으로 날아가고 속도는 우주선마다 다르며, 행성 표면에 닿는 순간 멈춘다. 로켓이 떨어진 지점에서 바이러스가 표면을 따라 시계 방향과 반시계 방향으로 같은 속도로 퍼지기 시작한다. 퍼지는 속도는 바이러스마다 다르다. 바이러스는 표면을 따라서만 이동하므로 행성 내부를 가로질러 반대편으로 가지 못한다.

표면의 모든 점에 바이러스가 하나라도 닿으면 행성은 완전히 감염된다. 완전히 감염될 때까지 걸리는 시간을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 행성의 반지름 $R$(미터)과 우주선의 수 $K$가 주어진다. 이어지는 $K$개 줄에는 각각 정수 네 개가 주어지며, 차례대로 우주선의 x좌표, y좌표, 로켓의 속도, 바이러스가 퍼지는 속도이다. 두 속도의 단위는 초당 미터이고, 퍼지는 속도는 표면을 따라 잰 값이다. 행성 내부에 있는 우주선은 없다.

$1 \le T \le 100$, $1 \le R \le 1000000$, $1 \le K \le 10000$이다. 두 좌표는 $-1000000$ 이상 $1000000$ 이하이고, 두 속도는 $1$ 이상 $1000000$ 이하이다.

각 테스트 케이스마다 행성이 완전히 감염될 때까지 걸리는 시간(초)을 소수점 아래 넷째 자리까지 반올림하여 한 줄에 출력한다.