#include <bits/stdc++.h>

using namespace std;

const int MX = 1000;
const long long INF = 1e18;

int a[MX][MX];
long long dp[MX][MX];

int main() {
	int T;
	ignore = scanf("%d", &T);
	while (T--) {
		int n;
		ignore = scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				ignore = scanf("%d", a[i] + j);
			
			sort(a[i], a[i] + n);
		}
		
		for (int i = 0; i < n; i++) dp[0][i] = a[0][i];
		for (int i = 1; i < n; i++)
			for (int j = 0, k = -1; j < n; j++) {
				while (k + 1 < n && a[i - 1][k + 1] < a[i][j]) k++;
				if (k == -1) dp[i][j] = -1 * INF;
				else dp[i][j] = a[i][j] + dp[i - 1][k];
			}
		
		printf("%lld\n", max(dp[n - 1][n - 1], -1ll));
	}
	
	return 0;
}