정사각형

평면 위에 축에 평행한 정사각형 $n$개가 있다. 각 정사각형은 왼쪽 아래 꼭짓점의 좌표 $(x, y)$와 한 변의 길이 $w$로 주어지며, 네 변은 각각 $x$축 또는 $y$축과 평행하다. 정사각형들은 크기가 서로 다를 수 있고, 서로 겹치거나 꼭짓점을 공유할 수도 있다.

각 정사각형에서 점을 정확히 하나씩 고른다. 이렇게 고른 점들의 집합에 대해 지름(diameter)은 두 점 사이 유클리드 거리의 최댓값으로 정의된다. 각 정사각형에서 점을 하나씩 고르는 여러 방법 중에서, 고른 점들의 지름이 최대가 되도록 하고 싶다.

이때 얻을 수 있는 최대 지름을 $D$라 하자. $D$의 제곱인 $D^2$을 정수로 출력하면 된다.

위 그림처럼 정사각형이 여섯 개 있을 때, 최대 지름은 서로 다른 두 정사각형에서 고른 두 꼭짓점 사이의 거리로 얻어진다. $D^2$은 항상 정수임이 보장된다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 정사각형의 개수 $n$이 주어진다 ($2 \le n \le 100{,}000$). 이어지는 $n$개의 줄에는 각 정사각형을 나타내는 세 정수 $x$, $y$, $w$가 주어진다. 여기서 $(x, y)$는 정사각형의 왼쪽 아래 꼭짓점 좌표이고 $w$는 한 변의 길이이다 ($0 \le x, y \le 10{,}000$, $1 \le w \le 10{,}000$).

각 테스트 케이스마다 한 줄에 하나씩, 정사각형마다 점을 하나씩 골랐을 때 얻을 수 있는 최대 지름 $D$의 제곱 $D^2$을 정수로 출력한다.