RAM (Rotating Auto-Mobiles)

테라와 루루는 과수원을 운영하고 있다.

과수원의 창고는 좌표평면의 원점 $(0, 0)$에 있고, 과수원에는 $N$그루의 사과나무가 있다. $i$번째 사과나무는 $(x_i, y_i)$에 있으며, 이 나무에서는 매일 $a_i$상자의 사과를 수확한다.

테라는 수확한 사과를 창고로 옮기기 위해 원형 운반기를 설치하려 한다. 원형 운반기는 하나의 원을 따라 움직이며, 사과를 모두 실은 뒤 창고에서 하역해야 하므로 이동 경로는 반드시 창고를 지나야 한다. 원의 중심과 반지름은 자유롭게 정할 수 있으며, 반지름이 $0$인 경로도 허용한다.

하루의 수확 작업은 다음과 같이 진행된다.

1. 원형 운반기는 정해진 원형 경로를 정확히 한 바퀴 돈다.
2. 각 사과나무에는 전용 수확 로봇이 한 대씩 배치된다. 수확 로봇은 사과 한 상자를 나무에서 원형 운반기의 경로까지 옮긴 뒤, 다시 나무로 돌아온다. 이때 로봇은 나무와 원형 경로 사이를 잇는 가장 짧은 경로를 이용한다.
3. $i$번째 사과나무의 수확 로봇은 이 작업을 $a_i$번 반복한다.

원형 운반기와 수확 로봇은 이동한 거리에 비례하여 마모된다. 특히 하루 동안 가장 많이 이동한 장비가 과수원 전체의 정비 주기를 결정하기 때문에, 특정 장비에 작업이 지나치게 집중되는 것은 좋지 않다.

루루는 원형 운반기의 경로를 적절히 정하여, 원형 운반기와 모든 수확 로봇이 하루 동안 이동하는 거리 중 최댓값을 최소화하려 한다.

이 최솟값을 구하여라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 20\,000$)

각 테스트 케이스는 다음과 같은 형식으로 주어진다.

첫째 줄에 사과나무의 수 $N$이 주어진다. ($1 \le N \le 20\,000$)

각 테스트 케이스마다, 원형 운반기와 모든 수확 로봇이 하루 동안 이동하는 거리 중 최댓값으로 가능한 최솟값을 한 줄에 하나씩 출력한다.

각 답에 대해 정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정한다.

아래 애니메이션은 각 장비가 하루 동안 이동하는 거리를 시각화한 것이다. 실제 작업 순서와는 무관하게, 이동거리의 비교를 위해 모든 장비가 같은 속력으로 움직이는 것으로 나타냈다.

예제 1에서는 중심이