Swap and Matrix Multiplication

Two $N\times N$ integer matrices $A$ and $B$ are given. You may perform the following operation at most once.

• Choose two integers $i,j$ and swap $A_{i,j}$ with $B_{j,i}$.

Let $C=A\times B$. Define the sum of the entries on or above the main diagonal of $C$ as

Find the maximum possible value of $S$ after performing the operation at most once.

The input is given in the following format:

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

For each case, print the maximum possible value of $S$ on one line.

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