Tour

$2$차원 평면 위에 $1$부터 $N$까지 번호가 매겨진 $N$개의 점이 있다. $i$번 점의 좌표는 $(X_i,Y_i)$이다. 두 점 사이 거리의 최댓값을 $D$라고 한다.

$(1,2,\cdots,N)$의 순열 $Q=(Q_1,Q_2,\cdots,Q_N)$에 대하여, 이 순열이 나타내는 순회의 길이 을 다음과 같이 정의한다. 단, 이다.

순열 $Q$를 잘 정하여 $\frac{L}{D}$를 작게 해야 한다. 자세한 내용은 Scoring 섹션을 참고하라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 한 줄에 $(1,2,\cdots,N)$의 순열 $(Q_1,Q_2,\cdots,Q_N)$을 공백으로 구분하여 출력한다.

• $1\le T\le200\,000$.
• $3\le N\le200\,000$.
• $-{10}^{12}$ ().

하나의 서브태스크에 포함된 각 테스트 케이스에 대해 다음 값을 계산한다.