관할 구역의 각성

정의와 용사 슈퍼리그(SLPC)는 부패한 정치인이 선거를 훔치려는 음모를 감시해 왔다. 지난 한 주 동안 이 정치인은 정신 조종 기술로 선거의 승자를 뽑는 대표 $n$명을 모두 조종하게 되었다. 다행히 SLPC는 당신을 영입하는 데 성공했고, 이제 정신 조종을 깨뜨리는 당신의 능력을 쓸 수 있다. 당신은 좌표축에 평행한 직사각형 하나 안에서 정신 조종을 깨뜨릴 수 있다. 안타깝게도 이 능력에는 큰 대가가 따른다. 다음 날 직사각형의 크기에 비례하는 두통을 앓게 된다. 하루에 능력을 여러 번 쓰면 무슨 일이 생길지는 생각하고 싶지도 않고, 그런 위험을 감수할 생각도 없다.

당신은 조사를 마쳐서 투표 직전에 각 대표가 서 있을 위치를 알고 있다. 정치인이 과반수(절반보다 엄격히 많은) 표를 얻지 못하도록 충분한 수의 대표를 풀어 주어야 한다. 이를 위해 능력을 적용할 수 있는 좌표축에 평행한 직사각형 중 넓이가 가장 작은 것의 넓이는 얼마인가?

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

각 테스트 케이스의 첫째 줄에는 대표의 수 $n$이 주어진다. ($1 \le n \le 299$, $n$은 홀수) 다음 $n$개의 줄에는 각 대표의 $x$ 좌표와 $y$ 좌표를 나타내는 두 정수가 주어진다. 모든 좌표는 $-10\,000$ 이상 $10\,000$ 이하이다.

각 테스트 케이스마다 대표를 $n/2$명보다 많이 포함하는 좌표축에 평행한 직사각형 중 가장 작은 넓이를 한 줄에 정수로 출력한다. 직사각형의 경계 위에 있는 대표도 포함된 것으로 보며, 폭이나 높이가 $0$인 직사각형도 허용된다.

첫 번째 테스트 케이스에서는 점 하나만 포함하는 직사각형의 넓이가 $0$이다.

두 번째 테스트 케이스에서는 직사각형이 적어도 두 점을 포함해야 한다. 가장 작은 직사각형은 두 가지이다. 하나는 $(0, 0)$과 $(1, 4)$를 포함하고, 다른 하나는 $(1, 4)$와 $(3, 2)$를 포함한다. 어느 쪽이든 넓이는 $4$이다.