题目描述

小 T 准备在家里摆放几幅画，为此他买来了 $N$ 幅画和 $N$ 个画框。为了体现他的品味，小 T 希望能合理地搭配画与画框，使得其显得既不过于平庸也不太违和。

对于第 $i$ 幅画与第 $j$ 个画框的配对，小 T 都给出了这个配对的平凡度 $A_{i, j}$ 与违和度 $B_{i, j}$ 。整个搭配方案的总体不和谐度为每对画与画框平凡度之和与每对画与画框违和度的乘积。具体来说，设搭配方案中第 $i$ 幅画与第 $P_i$ 个画框配对，则总体不和谐度为

$$\mathrm{disharmony}=\sum_{i=1}^{N}A_{i,p_i}\times \sum_{i=1}^{N}B_{i,p_i} $$

小 T 希望知道通过搭配能得到的最小的总体不和谐度是多少。

输入格式

输入文件第 $1$ 行是一个正整数 $T$，表示数据组数，接下来是 $T$ 组数据。对于每组数据，第 $1$ 行是一个正整数 $N$，表示有 $N$ 对画和画框。第 $2$ 到第 $N+1$ 行，每行有 $N$ 个非负整数，第 $i+1$ 行第 $j$ 个数表示 $A_{i, j}$。第 $N+2$ 到第 $2N+1$ 行，每行有 $N$ 个非负整数，第 $i+N+1$ 行第 $j$ 个数表示 $B_{i, j}$ 。

输出格式

包含 $T$ 行，每行一个整数，表示最小的总体不和谐度。

1
3
4 3 2
2 3 4
3 2 1
2 3 2
2 2 4
1 1 3

30

提示

第 $1$ 幅画搭配第 $3$ 个画框，第 $2$ 幅画搭配第 $1$ 个画框，第 $3$ 幅画搭配第 $2$ 个画框，则总体不和谐度为 $30$。

对于 $100\%$ 的数据，$N\leq 70$，$T\leq 3$，$A_{i, j}\leq 200$，$B_{i, j}\leq 200$。