/*
Ū������������Ū��
��Ҫ�����κ�һ��֣�
��д�����������������ʣ�
���������⣡
int <-> long long �����С�� MLE?RE? OK
ͼ�ۣ�DP�� 
�Ż�һ�£� 
*/

#include <bits/stdc++.h>

#define int long long

#define PII pair<int,int>

#define mkp make_pair

using namespace std;

const int N=1e5+10;

int n;
vector<PII> a[N];//ÿ��a[i]�洢����PII���ǵ����¶������򣡼ǵü�¼��� OK
priority_queue<PII,vector<PII>,greater<PII> > q[4],empt;//ÿ��PII�洢��ֵ�ͱ�ţ�ָ�����ĸ���
int res;//��ǰ�Ĵ� 
int point_pla[N];//����ȡ�������� 

void init() {
	q[1]=q[2]=q[3]=empt;
	for(int i=1;i<=n;++i) {
		a[i].clear();
	}
	for(int i=1;i<=n;++i) {
		point_pla[i]=0;
	}
	res=0;
	n=0;
} 

void readin() {
	cin>>n;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=3;++j) {
			PII rd;
			cin>>rd.first;
			rd.second=j;
			a[i].push_back(rd);
		}
	}
}

bool cmp(const PII& pr1,const PII& pr2) {
	if(pr1.first==pr2.first) {
		return pr1.second<pr2.second;
	}
	return pr1.first>pr2.first;//�Ӵ�С���� 
}

bool check() {
	if(max(q[1].size(),max(q[2].size(),q[3].size()))<=n/2) return true;
	return false;
}

void preprocess() {
	//Ԥ���������򣬷Ž�����Ķ�
	for(int i=1;i<=n;++i) {
		sort(a[i].begin(),a[i].end(),cmp);
		res+=a[i][0].first;//ͳ��΢��֮ǰ�Ĵ�
//		cout<<i<<":\n"; 
//		for(int j=0;j<3;++j) {
//			cout<<a[i][j].first<<" "<<a[i][j].second<<"\n";
//		}
//		cout<<"---------------\n";
	} 
	for(int i=1;i<=n;++i) {
		q[a[i][0].second].push(mkp(a[i][0].first-a[i][1].first,i));//�����ֵ���Ž�ȥ 
	}
//	cerr<<"original res:\n"<<res<<"\n";
	while(!check()) {
		for(int i=1;i<=3;++i) {
			//���ÿ����
			if(q[i].size()<=n/2) continue;
//			cerr<<"Here!"<<" "<<i<<"\n";
			//�϶����Ϸ��Ķ�
			while(q[i].size()>n/2) {
				PII p=q[i].top();
				q[i].pop();
//				cerr<<"remove:"<<p.second<<"\n";
				point_pla[p.second]++;
				res-=p.first;//ɾ��ԭ���Ĺ��� 
				//ͳ�Ʋ�ֵ���ŵ���һ������
				point_pla[p.second]++;//�ŵ���һ������ 
				int ord=a[p.second][point_pla[p.second]].second;//ͳ����һ���ŵ�����
				int new_diff=a[p.second][point_pla[p.second]].first-
				a[p.second][point_pla[p.second]+1].first;//ͳ���µĲ�ֵ 
				if(point_pla[p.second]==2) new_diff=1e9;
				else new_diff=new_diff; 
				q[ord].push(mkp(new_diff,p.second)); 
			}

		}
	}
}

void output() {
	cout<<res<<"\n"; 
}

signed main() {
	freopen("club.in","r",stdin);
	freopen("club.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--) {
		init();
		readin();
		preprocess();
		output();	
	}

	return 0;
} 
