小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 $n$ 个新成员，其中 $n$ 为偶数。现在小 L 希望将他们分到协会不同的部门。

算法协会共设有三个部门，其中第 $i$（$1 \le i \le n$）个新成员对第 $j$（$1 \le j \le 3$）个部门的满意度为 $a_{i,j}$。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，即若将第 $i$ 个新成员分配到第 $d_i \in \{1,2,3\}$ 个部门，则满意度为 $\sum_{i=1}^{n} a_{i,d_i}$。

小 L 不希望某一个部门的新成员数量过多。具体地，他要求分配方案中不存在一个部门被分配多于 $n/2$ 个新成员。你需要帮助小 L 求出满足要求的分配方案的满意度的最大值。

注：原评测使用文件输入输出（club.in / club.out），本站提交请使用标准输入输出，程序中不要写文件重定向代码。原题提交文件名：club.cpp，编译选项 -O2 -std=c++14 -static。

本题包含多组测试数据。

输入的第一行包含一个正整数 $t$，表示测试数据组数。接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 $n$，表示新成员的数量。
• 第 $i+1$（$1 \le i \le n$）行包含三个非负整数 $a_{i,1}, a_{i,2}, a_{i,3}$，分别表示第 $i$ 个新成员对第 $1,2,3$ 个部门的满意度。

对于每组测试数据，输出一行一个非负整数，表示满足要求的分配方案的满意度的最大值。

【样例 1 解释】

该样例共包含三组测试数据。第一组可将四个新成员分别分配到第 1,3,1,2 个部门，各部门人数 2,1,1，均不超过 $4/2=2$，满意度 $4+4+5+5=18$。第二组分配到第 1,1,2,2 个部门，满意度 $0+0+2+2=4$。第三组分配到第 2,1 个部门，满意度 $9+4=13$。

【数据范围】

• $1 \le t \le 5$；
• $2 \le n \le 10^5$，且 $n$ 为偶数；
• 对所有 $1 \le i \le n$，$1 \le j \le 3$，均有 $0 \le a_{i,j} \le 2 \times 10^4$。

测试点 20 个等分。特殊性质 A：所有 $a_{i,2}=a_{i,3}=0$；B：所有 $a_{i,3}=0$；C：$a_{i,j}$ 在 $[0,2\times10^4]$ 中独立均匀随机生成。

原题另有附加样例 club2~club5（已收录为本题测试点）。