교환과 행렬곱

$N\times N$ 정수 행렬 $A$, $B$가 주어진다. 다음 연산을 최대 한 번 수행할 수 있다.

• 두 정수 $i,j$를 고르고, $A_{i,j}$와 $B_{j,i}$를 서로 교환한다.

$C=A\times B$라 하고, 행렬 $C$의 주대각선 위쪽에 있는 원소와 주대각선에 있는 원소의 합을 다음과 같이 정의하자.

연산을 최대 한 번 수행하여 얻을 수 있는 $S$의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 케이스마다 $S$의 최댓값을 한 줄에 출력한다.

• $1\leq T\leq10\,000$.
• $1\leq N\leq1\,000$.
• $-100\le {}_{}$ ().