삼엽충은 지하철 건설을 매우 좋아합니다. 그는 $n$개의 노선을 설계했으며, 각 노선마다 평면 좌표로 나타낼 수 있는 $n+1$개의 역 후보지가 있습니다.

지하철 이용 경험을 풍부하게 하기 위해, 삼엽충은 각 노선을 하나의 선분으로 만들기로 결정했습니다! 즉, 각 노선에 대해 삼엽충은 오직 두 개의 역만을 선택하여 그 두 역을 잇는 선분을 만듭니다. 승객들의 환승 불편함을 극대화하기 위해, 삼엽충은 건설된 $n$개의 지하철 노선 사이의 교점 개수가 최소가 되기를 원합니다. 교점에는 시작점과 끝점도 포함됨에 유의하십시오. 적절한 계획을 세워보세요.

요약: 2차원 평면상에 $n$가지 색상의 점이 각각 $n+1$개씩 주어집니다. 각 색상마다 서로 다른 두 점을 선택하여 선분을 연결하되, 모든 $n$개의 선분 사이의 교점 개수가 최소가 되도록 하십시오. 구성 방법을 출력하세요.

주의: 두 선분이 공선(collinear)일 경우, 교점의 개수는 무한대로 정의합니다. 모든 무한대는 서로 같은 것으로 간주합니다.

입력

입력은 여러 개의 테스트 케이스로 구성됩니다. 첫 번째 줄에 테스트 케이스의 개수 $T$가 주어집니다. 각 테스트 케이스에 대하여:

첫 번째 줄에 노선의 개수 $n$이 주어집니다.

다음 $n$개의 줄에는 각각 $2n+2$개의 정수가 주어집니다. 여기서 $2i-1$번째와 $2i$번째 정수는 현재 노선의 $i$번째 역의 좌표 $(x_i, y_i)$를 나타내며, 해당 역의 번호는 $i$입니다.

모든 역의 좌표는 서로 다름이 보장됩니다.

출력

각 테스트 케이스마다 $n$개의 줄을 출력합니다. 각 줄에는 해당 노선이 연결하는 두 역의 번호를 공백으로 구분하여 출력하십시오. 임의의 해를 출력하면 됩니다.

예제

입력 1

1
2
5 0 0 8 10 8
0 4 10 4 5 12

출력 1

1 3
1 3

참고

그림에서 파란색과 빨간색 점은 각각 1번 노선과 2번 노선의 역을 나타내며, 파란색 선과 빨간색 선은 각각 1번 노선과 2번 노선이 선택한 경로를 나타냅니다.

임의의 해를 출력하면 되므로, 아래와 같이 출력해도 정답입니다.

1 2
2 3

제한

| :--------: | :--------: | :----------------------------------------------------------: | | 서브태스크 번호 | 배점 | 추가 제한 | | 1 | 30 | $n\le 5, \sum n\le 50$ | | 2 | 20 | 이 $n(n+1)$개의 점을 배치하여 $i$번째 점의 좌표가 정확히 $(i, i)$가 되는 경우가 존재함 | | 3 | 20 | $n\le 100$ | | 4 | 30 | 없음 |

모든 데이터에 대하여: $1\le n\le 1000, \sum n\le 2000$, $|x_i|, |y_i|\le 10^9$입니다.