Little T is preparing to hang several paintings in his home, and for this purpose, he has purchased $N$ paintings and $N$ frames. To reflect his taste, Little T hopes to reasonably pair the paintings with the frames so that they appear neither too mediocre nor too discordant. For the pairing of the $i$-th painting with the $j$-th frame, Little T has provided a "mediocrity" value $A_{i,j}$ and a "discordance" value $B_{i,j}$. The total disharmony of the entire arrangement is the product of the sum of the mediocrity values of all pairs and the sum of the discordance values of all pairs. Specifically, if the $i$-th painting is paired with the $P_i$-th frame in the arrangement, the total disharmony is:
$$disharmony = \left( \sum_{i=1}^{N} A_{i,P_i} \right) * \left( \sum_{i=1}^{N} B_{i,P_i} \right)$$
Little T wants to know the minimum total disharmony that can be achieved through such a pairing.
Input
The first line contains a positive integer $T$, representing the number of test cases.
The following are $T$ test cases. For each test case: The first line is a positive integer $N$, representing the number of paintings and frames. The next $N$ lines (from line 2 to $N+1$) each contain $N$ non-negative integers, where the $j$-th number in the $(i+1)$-th line represents $A_{i,j}$. The next $N$ lines (from line $N+2$ to $2N+1$) each contain $N$ non-negative integers, where the $j$-th number in the $(i+N+1)$-th line represents $B_{i,j}$.
Output
The output contains $T$ lines, each containing a single integer representing the minimum total disharmony.
Examples
Input 1
1 3 4 3 2 2 3 4 3 2 1 2 3 2 2 2 4 1 1 3
Output 1
30
Note
The 1st painting is paired with the 3rd frame, the 2nd painting is paired with the 1st frame, and the 3rd painting is paired with the 2nd frame. The total disharmony is $(2+2+2)*(2+2+1)=30$.
Constraints
For 10% of the data, $N \le 10, T \le 2$; For 30% of the data, $A_{i,j} = B_{i,j}$; For 70% of the data, $N \le 40$; For 100% of the data, $N \le 70, T \le 3, A_{i,j} \le 200, B_{i,j} \le 200$.