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

문제

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

고객이 살고 있는 위치는 정수로 된 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)가 주어진다. 모든 값은 정수이다.

출력

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

예제 입력 1

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

예제 출력 1

10 4
3987543098 3975087573110998514
W3sicHJvYmxlbV9pZCI6IjkxMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWFjZTRcdWQ1NWMgXHVjNjc4XHVkMzEwXHVjNmQwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWI3OWMgXHVjMmRjXHVhYzA0IFx1YjNkOVx1YzU0OCBcdWM1ZWNcdWQ1ODlcdWQ1NzRcdWM2MjRcdWIzNTggXHVjNjc4XHVkMzEwXHVjNmQwXHVjNzQwIFx1YjEwOFx1YmIzNCBcdWQ1M2NcdWFjZTRcdWQ1NzRcdWM4MzhcdWMxMWMgXHVjNzc0XHVjODFjIFx1ZDU1YyBcdWFjZjNcdWM1ZDAgXHVjODE1XHVjYzI5XHVkNTU4XHVjNWVjIFx1YzlkMVx1Yzc0NCBcdWMxMzhcdWM2YjBcdWFjZTAgXHVhY2UwXHVhYzFkXHViNGU0XHVjNWQwXHVhYzhjIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM5ZDFcdWM1ZDAgXHViYzI5XHViYjM4XHVkNTU4XHViM2M0XHViODVkIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YWMxZFx1Yzc3NCBcdWMwYjRcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWM4MTVcdWMyMThcdWI4NWMgXHViNDFjIHgsIHkgXHVjODhjXHVkNDVjXHViOTdjIFx1YWMwMFx1YzljMFx1YmE3MCwgXHViYWE4XHViNGUwIFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViMmU0LiBcdWM2NzhcdWQzMTBcdWM2ZDBcdWIzYzQgXHVjODE1XHVjMjE4IFx1Yzg4Y1x1ZDQ1YyBcdWM3MDRcdWM1ZDAgXHVjOWQxXHVjNzQ0IFx1YzljMFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YzViNFx1YjVhNCBcdWFjZTBcdWFjMWRcdWM3NTggXHVjOWQxXHVhY2ZjXHViM2M0IFx1YWRmOCBcdWM3MDRcdWNlNThcdWFjMDAgXHVhY2I5XHVjY2QwXHVjMTFjXHViMjk0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWFjMDEgXHVhY2UwXHVhYzFkXHVjNzc0IFx1YzY3OFx1ZDMxMFx1YzZkMFx1Yzc1OCBcdWM5ZDFcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHViODI0XHViYTc0IFx1YjllOFx1ZDU1OFx1ZDBjNCBcdWFjNzBcdWI5YWMsIFx1Yzk4OSBcdWM2NzhcdWQzMTBcdWM2ZDBcdWM3NTggXHVjOWQxIFx1YzcwNFx1Y2U1OFx1YWMwMCAoeCwgeSlcdWM3NzRcdWFjZTAgXHVhY2UwXHVhYzFkXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCAoeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+KVx1Yzc3YyBcdWI1NGMgfHggJm1pbnVzOyB4PHN1Yj5pPFwvc3ViPnwgKyB8eSAmbWludXM7IHk8c3ViPmk8XC9zdWI+fFx1YjljY1x1ZDA3Y1x1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVhY2UwXHVhYzFkXHVjNzU4IFx1Yzc3NFx1YjNkOVx1YWM3MFx1YjlhYyBcdWQ1NjlcdWM3NzQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YWM4YyBcdWQ1NThcdWIyOTQgXHVjNzA0XHVjZTU4XHViMjk0IFx1YmE4NyBcdWFkNzBcdWIzNzBcdWIwOTggXHVjODc0XHVjN2FjXHVkNTYwXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKCZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzViNFx1YzExYyBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjZTBcdWFjMWRcdWM3NTggXHVjMjE4IG4oMSAmbGU7IG4gJmxlOyAyIDAwMCksIFx1Yzc3NFx1YzViNFx1YzExYyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBpXHViYzg4XHVjOWY4IFx1YWNlMFx1YWMxZFx1Yzc1OCBcdWM3MDRcdWNlNTggeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+KCZtaW51czsxMDAwMDAwMDAwICZsZTsgeDxzdWI+aTxcL3N1Yj4seTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMDAwMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWFjMTJcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YmFhOFx1YjRlMCBcdWFjZTBcdWFjMWRcdWM3NTggXHVjNzc0XHViM2Q5XHVhYzcwXHViOWFjIFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTIsIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWQ1NjlcdWM3NzQgXHViMDk4XHVjNjI0XHVhYzhjIFx1ZDU1OFx1YjI5NCBcdWM2NzhcdWQzMTBcdWM2ZDAgXHVjOWQxXHVjNzU4IFx1YzcwNFx1Y2U1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MTI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2V0dGxpbmcgU2FsZXNtYW4gUHJvYmxlbSIsImRlc2NyaXB0aW9uIjoiPHA+QWZ0ZXIgdHJhdmVsbGluZyBhcm91bmQgZm9yIHllYXJzLCBTYWxlc21hbiBKb2huIGhhcyBkZWNpZGVkIHRvIHNldHRsZS4gSGUgd2FudHMgdG8gYnVpbGQgYSBuZXcgaG91c2UgY2xvc2UgdG8gaGlzIGN1c3RvbWVycywgc28gaGUgZG9lc24mcnNxdW87dCBoYXZlIHRvIHRyYXZlbCBhcyBtdWNoIGFueSBtb3JlLiBMdWNraWx5IEpvaG4ga25vd3MgdGhlIGxvY2F0aW9uIG9mIGFsbCBvZiBoaXMgY3VzdG9tZXJzLjxcL3A+XHJcblxyXG48cD5BbGwgb2YgdGhlIGN1c3RvbWVycyZyc3F1bzsgbG9jYXRpb25zIGFyZSBhdCAoZGlzdGluY3QpIGludGVnZXIgY29vcmRpbmF0ZXMuIEpvaG4mcnNxdW87cyBuZXcgaG91c2Ugc2hvdWxkIGFsc28gYmUgYnVpbHQgb24gaW50ZWdlciBjb29yZGluYXRlcywgd2hpY2ggY2Fubm90IGJlIHRoZSBzYW1lIGFzIGFueSBvZiB0aGUgY3VzLSB0b21lcnMmcnNxdW87IGxvY2F0aW9ucy4gU2luY2UgSm9obiBsaXZlcyBpbiBhIGxhcmdlIGFuZCBjcm93ZGVkIGNpdHksIHRoZSB0cmF2ZWxsaW5nIGRpc3RhbmNlIHRvIGFueSBjdXN0b21lciBpcyB0aGUgTWFuaGF0dGFuIGRpc3RhbmNlOiB8eCAmbWludXM7IHg8c3ViPmk8XC9zdWI+fCArIHx5ICZtaW51czsgeTxzdWI+aTxcL3N1Yj58LCB3aGVyZSAoeCwgeSkgYW5kICh4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4pIGFyZSB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIG5ldyBob3VzZSBhbmQgYSBjdXN0b21lciByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPldoYXQgaXMgdGhlIG51bWJlciBvZiBsb2NhdGlvbnMgd2hlcmUgSm9obiBjb3VsZCBzZXR0bGUsIHNvIHRoZSBzdW0gb2YgdGhlIGRpc3RhbmNlIHRvIGFsbCBvZiBoaXMgY3VzdG9tZXJzIGlzIGFzIGxvdyBhcyBwb3NpYmxlPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgYW4gaW50ZWdlciB0ICgxICZsZTsgdCAmbGU7IDEwMCk6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gVGhlbiBmb3IgZWFjaCB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMiAwMDApOiB0aGUgbnVtYmVyIG9mIGN1c3RvbWVycyBKb2huIGhhcy48XC9saT5cclxuXHQ8bGk+biBsaW5lcyB3aXRoIHR3byBpbnRlZ2VycyB4PHN1Yj5pPFwvc3ViPiBhbmQgeTxzdWI+aTxcL3N1Yj4gKCZtaW51czsxMDAwMDAwMDAwICZsZTsgeDxzdWI+aTxcL3N1Yj4seTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMDAwMDAwKTogdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBpLXRoIGN1c3RvbWVyLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IHRoZSBtaW5pbXVtIHN1bW1lZCBkaXN0YW5jZSB0byBhbGwgY3VzdG9tZXJzLCBhbmQgdGhlIG51bWJlciBvZiBzcG90cyBvbiB3aGljaCBKb2huIGNhbiBidWlsZCBoaXMgbmV3IGhvdXNlIHRvIGFjaGlldmUgdGhpcyBtaW5pbXVtLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d