16706번 - 의약품 수송 2 스페셜 저지

표면 대부분을 사막이 차지하는 미개척 행성에 두 탐사대가 파견되어 개척지를 세웠다. 이 사막은 매우 황량하여 모래 바람이 세차게 불기 때문에 두 개척지는 모두 지하에 건설되었다. 개척지에 출입하기 쉽도록 탐사대는 지면까지 탐사 차량을 운반할 수 있는 수직 리프트를 설치했다. 평소에는 리프트가 올라간 상태로 있다가, 개척지에서 지상으로 올라갈 땐 리프트가 내려오고 차량을 싣고 나서 다시 리프트를 올려보낸다. 반대로 지상에서 개척지로 내려오려면 차량을 리프트에 태운 다음 리프트를 하강시킨다. 

탐사 차량은 앞뒤로 길고, 리프트도 차량 크기에 딱 맞춰 한 쪽은 짧고 다른 쪽은 긴 직사각형 모양이기 때문에 차량을 리프트에 싣는 방법은 두 가지 뿐이다. 예를 들어 리프트의 긴 변이 동서 방향이라면 차량 앞면이 동쪽 또는 서쪽을 향하게 리프트에 실을 수 있다. 이 상태로 지상에 나가면 탐사 차량은 동쪽 또는 서쪽으로 출발할 수 있다. 역으로, 지상에서 임무를 마친 차량이 개척지로 돌아오려면 반드시 동쪽 또는 서쪽을 바라보면서 리프트에 타야 한다. 개척지로 돌아오는 게 아니라면 리프트 위를 어긋난 방향으로 지날 수 있다.

탐사가 진행되는 도중 한 개척지에서 환자가 발생하여 다른 개척지로부터 의약품을 수송받으려 한다. 탐사 차량이 최대한 빨리 의약품을 수송할 수 있도록 최단 경로를 구해주자. 탐사 차량이 좌회전이나 우회전할 때 최소 곡률 반지름은 R이고(즉, 운전대를 왼쪽이나 오른쪽으로 끝까지 꺾으면 차량이 반지름 R인 원을 따라 주행한다), 탐사 차량은 후진할 수 없다. 행성 표면은 2차원 평면으로 가정한다.

첫째 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 100)

테스트케이스의 첫째 줄에는 R이 주어진다. (1 ≤ R ≤ 100)

테스트케이스의 둘째 줄에는 출발하는 개척지의 리프트의 좌표 x₁, y₁과 리프트의 긴 변이 x축 양의 방향과 반시계 방향으로 이루는 각도 θ₁이 주어진다.

테스트케이스의 셋째 줄에는 도착해야 할 개척지의 리프트의 좌표 x₂, y₂와 리프트의 긴 변이 x축 양의 방향과 반시계 방향으로 이루는 각도 θ₂가 주어진다.

(0 ≤ x₁, y₁, x₂, y₂ ≤ 100; 0 ≤ θ₁, θ₂ < 180)

주어지는 값은 모두 정수이며, 두 리프트는 위치가 같지 않다.

출발 개척지의 리프트에서 도착 개척지의 리프트까지 가는 최단 경로의 길이를 각 테스트케이스마다 한 줄에 하나씩 출력한다. 절대/상대 오차는 10^-4까지 허용한다.