Problem Statement

In the AtCoder World Tour Finals 2800, $N$ contestants participated, and a total of five problems were presented. Each problem is assigned an integer score of at least $1$ point, and the problems are numbered so that the scores are non-decreasing from problem $1$ to problem $5$. There are no partial points. Similar to the usual AtCoder rules, ranking is done as follows. In this problem, we do not consider the situation where multiple contestants have the same total score and penalty.

RankingThe contestant with the higher total score ranks higher. In case of a tie, the one with the smaller penalty ranks higher.

Now, Aoki, a reporter covering the finals, noted the following information:

1. The number of participants $N$.
2. Which problems each contestant solved. $A_{i,j}=1$ means the $i$-th contestant $(1 \leq i \leq N)$ correctly solved problem $j$, and $A_{i,j}=0$ means they did not.
3. The rank of each contestant. The $i$-th contestant $(1 \leq i \leq N)$ was ranked $R_i$-th.

However, when he started writing the article, he realized he did not note the scores and penalties. Furthermore, he realized there might be inconsistencies in the information he noted. Now, solve the following problem.

Assume that he correctly noted information 1 and 2. Let $D_i$ be the actual rank of contestant $i$ $(1 \leq i \leq N)$, and find the minimum possible total squared error $(D_1 - R_1)^2 + (D_2 - R_2)^2 + \dots + (D_N - R_N)^2$.

You have $T$ test cases to process.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 3 \times 10^5$
• Each of $A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}, A_{i,5}$ is $0$ or $1$ $(1 \leq i \leq N)$.
• The sum of $A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}, A_{i,5}$ is at least $1$ $(1 \leq i \leq N)$.
• $1 \leq R_i \leq N$ $(1 \leq i \leq N)$
• $R_1, R_2, \dots, R_N$ are distinct.
• The total value of $N$ across all test cases is at most $3 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format. Here $\mathrm{case}_i$ represents the $i$-th test case $(1 \leq i \leq T)$.

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
A_{1,1} A_{1,2} A_{1,3} A_{1,4} A_{1,5}
A_{2,1} A_{2,2} A_{2,3} A_{2,4} A_{2,5}
\vdots
A_{N,1} A_{N,2} A_{N,3} A_{N,4} A_{N,5}
R_1 R_2 \cdots R_N

Output

Print the answers.