小工是学校算法协会的成员。在今年的学校社团招新中，小一共招收了个新
成员，其中几为偶数。现在小工希望将他们分到协会不同的部门。算法协会共设有三个部门，其中第i(1≤i≤n)个新成员对第j(1≤j≤3)个部门的满意度为“。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第i(1<i≤n)个新成员分配到了第d€{1,2,3}个部门，则该分配方案的满意度为
小工不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于n/2号个新成员。你需要帮助小工求出，满足他要求的分配方案的满意度的最大值。
输入的第一行包含一个正整数t，表示测试数据组数。接下来依次输入每组测试数据，对于每组测试数据: 第一行包含一个正整数n，表示新成员的数量。 。第i+1(1≤i≤n)行包含三个非负整数 ai1,ai2,ai3，分别表示第i个新成员对第1，2，3个部门的满意度。
对于每组测试数据，输出一行一个非负整数，表示满足小工要求的分配方案的满意度的最大值。
3 4 2 1 3 2 4 5 3 4 3 5 1 4 0 1 0 0 1 0 0 2 0 0 2 0 2 10 9 8 4 0 0
18 4 13
样例1解释
该样例共包含三组测试数据。 对于第一组测试数据，可以将四个新成员分别分配到第1，3，1，2个部门，则三个部门的新成员数量分别为2，1，1，均不超过4/2=2，满意度为4+4+5+5=18。
对于第二组测试数据，可以将四个新成员分别分配到第1,1,2,2个部门，则三个部门的新成员数量分别为2，2，0，均不超过4/2=2，满意度为0+0+2+2=4。 对于第三组测试数据，可以将两个新成员分别分配到第2,1个部门，则三个部门的新成员数量分别为1,1,0，均不超过2/2=1，满意度为9+4=13。
