该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

$\hspace{15pt}$现有一个 $3$ 行 $n$ 列的二维非负整数数组，其中：

1. 数组元素的取值范围为 $1$ 到 $n$，且每个整数从 $1$ 到 $n$ 在数组中恰好出现三次。

2. 定义「胆小数组 $B$」：对于每个索引 $i（0 \leq i \leq n）$，$B_{i}$ 是该二维数组第 $i$ 列 3 个元素中的最小值。

$\hspace{15pt}$定义「胆小值」为：

1. 从 $B$ 数组中选择元素构成最长合格排列，其长度为 $k$。

2. 计算该最长合格排列的胆小值，包含两部分：

• 对于每个 $x （1 \leq x \leq k）$，从 $B$ 所有等于 $x$ 的元素中，选择元素 $B_{i}$ 对应的二维数组所在列的另外两个元素之和减去 $B_{i}$ 的最小值 $min_{x}$，将这些最小值累加；
• 对于每个 $x （1 \leq x \leq k）$，累加二维数组中所有值等于 $x$ 的元素所在「行数」的总和 $r_{x}$（行数定义：第 1 行对应 1，第 2 行对应 2，第 3 行对应 3）。

$\hspace{15pt}$两部分之和即为该数组的「胆小值」。即：

$\hspace{15pt}$ $$胆小值 =\sum_{x=1}^{k} min_x + \sum_{x=r}^{k} r_x$$

$\hspace{15pt}$现在给定数组，请你计算胆小值。

【排列】长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，$\{2,3,1,5,4\}$ 是一个长度为 5 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

Format

Input

$\hspace{15pt}$第一行包含一个整数 $t（1 \leq t \leq 10）$，表示测试样例中二维数组的组数。

$\hspace{15pt}$每组的第一行包含一个整数 $n （1 \leq n \leq 3000）$，表示数组的列数。

$\hspace{15pt}$接下来3行，每行包含 $n$ 个整数。

$\hspace{15pt}$ps：样例保证二维数组元素的取值范围为 1 到 n，且每个整数从 $1$ 到 $n$ 在二维数组中$\textbf{恰好出现三次}$。

Output

$\hspace{15pt}$每组每行输出一个整数，表示该数组的「胆小值」。

Samples

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

23
7

Note

$\hspace{15pt}$根据所给的二维数组可以得出其胆小数组 $B = \{1,2,1,1 \}$

$\hspace{15pt}$所以可以从 $B$ 中选择元素组成的最长合格排列为 ${1,2}$, 所以 $k = 2$.

$\hspace{15pt}$开始计算胆小值：

• 当 $x = 1$ 时，$min_{x} = 5,\,r_{x} = 7$ ;
• 当 $x = 2$ 时，$min_{x} = 4,\, r_{x} = 7$ ;

$\hspace{15pt}$胆小值 $= min_{1} + r_{1} + min_{2}+r_{2} = 23$