다리 놓기

최근 큰 태풍이 지나가면서 섬과 섬을 잇던 다리가 모두 사라졌습니다. 이미 벌어진 일은 어쩔 수 없으니, 이제 도로망을 다시 세워야 합니다. 정부는 응급 복구 계획으로, 사람들이 어떤 두 섬 사이든 물에 젖지 않고 오갈 수 있도록 다리를 놓기로 했습니다. 다시 말해 모든 섬이 다리를 통해 서로 연결되어야 합니다.

길이가 $x$인 다리를 놓는 비용은 $x^2$입니다. 두 섬을 잇는 다리의 길이는 두 섬 사이의 가장 짧은 직선 거리, 즉 두 직사각형에서 가장 가까운 두 점 사이의 유클리드 거리입니다. 다리는 원하는 만큼 놓을 수 있으며, 모든 섬이 서로 오갈 수 있도록 연결하면서 전체 비용의 합을 최소로 만들어야 합니다.

간척 사업 덕분에 모든 섬은 각 변이 좌표축과 평행한 직사각형입니다. 섬들의 위치와 모양이 주어질 때, 모든 섬을 연결하는 데 드는 최소 비용을 구하세요.

그림 1. 다리로 섬들을 연결하는 예시.

첫 번째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어집니다.

각 테스트 케이스의 첫 줄에는 섬의 수 $N$ ($2 \le N \le 5000$)이 주어집니다. 이어지는 $N$개의 줄에는 각각 네 정수 $x$, $y$, $w$, $h$ ($0 \le x, y, w, h \le 10000$)가 주어지며, $(x, y)$는 한 섬의 왼쪽 위 꼭짓점, $w$와 $h$는 그 섬의 너비와 높이입니다. 이 섬은 $x \le p \le x + w$이고 $y - h \le q \le y$인 모든 점 $(p, q)$를 덮습니다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력합니다. 이는 모든 섬을 연결하는 최소 비용입니다.