시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

오랜 시간 동안 여행해오던 외판원은 너무 피곤해져서 이제 한 곳에 정착하여 집을 세우고 고객들에게 자신의 집에 방문하도록 하려고 한다.

고객이 살고 있는 위치는 정수로 된 x, y 좌표를 가지며, 모든 위치는 서로 다르다. 외판원도 정수 좌표 위에 집을 지어야 하며, 어떤 고객의 집과도 그 위치가 겹쳐서는 안 된다. 또한 각 고객이 외판원의 집을 방문하려면 맨하탄 거리, 즉 외판원의 집 위치가 (x, y)이고 고객의 위치가 (xi, yi)일 때 |x − xi| + |y − yi|만큼을 이동해야 한다.

모든 고객의 이동거리 합이 최소가 되게 하는 위치는 몇 군데나 존재할까?

입력

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

이어서 각 테스트 케이스마다, 첫째 줄에 고객의 수 n(1 ≤ n ≤ 2 000), 이어서 n개의 줄에 i번째 고객의 위치 xi, yi(−1000000000 ≤ xi,yi ≤ 1000000000)가 주어진다. 모든 값은 정수이다.

출력

각 테스트 케이스마다 모든 고객의 이동거리 합의 최솟값, 그러한 합이 나오게 하는 외판원 집의 위치 개수를 공백으로 구분하여 한 줄에 출력한다.

예제 입력

2
4
1 -3
0 1
-2 1
1 -1
2
-999888777 1000000000
1000000000 -987654321

예제 출력

10 4
3987543098 3975087573110998514

힌트