#include<bits/stdc++.h>
using namespace std;

int T;
int a[9],b[9],c[9];
string s;

bool solve()
{
	for (int i = 0 ; i < 9 ; i ++) {
		if (a[i] >= 2 || b[i] >= 2 || c[i] >= 2) return false;
		if (i == 0) continue;
		if (a[i-1] && a[i]) return false;
		if (b[i-1] && b[i]) return false;
		if (c[i-1] && c[i]) return false;
	}
	return true;
}

int main()
{
	cin >> T;
	while (T --) {
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		memset(c, 0, sizeof(c));
		for (int i = 0 ; i < 7 ; i ++) {
			cin >> s;
//			cout << s << "  ";
			if (s[1] == 'W') a[s[0]-'1'] ++;
			else if (s[1] == 'B') b[s[0]-'1'] ++;
			else if (s[1] == 'T') c[s[0]-'1'] ++;
		}
//		cout << c[0];
		bool f = solve();
		if (f) cout << "YES\n"; else cout << "NO\n";
	}
} 

/**

4
1T 4T 7T 2B 5B 8B 9W
1T 2T 3T 4T 5T 6T 7T
1B 2W 3T 4B 5W 6T 8W
2B 8B 5B 2B 6T 7W 4W

YES
NO
YES
NO

**/

#include<bits/stdc++.h>
using namespace std;

int N,M,r,c;
int a[501][501];
int row[501], col[501];
int sufr[501], sufc[501];
set<int> rr, cc;

int main()
{
	scanf("%d",&N);
	for (int i = 1 ; i <= N ; i ++)
		for (int j = 1 ; j <= N ; j ++)
			scanf("%d",&a[i][j]);
		
	for (int i = 1 ; i <= N ; i ++)
		for (int j = 1 ; j <= N ; j ++)
			row[i] += a[i][j], col[i] += a[j][i];
				
//	for (int i = 1 ; i <= N ; i ++) printf("%d %d  ", row[i], col[i]); 
	for (int i = 1 ; i <= N ; i ++) rr.insert(i), cc.insert(i), sufr[i] = 1, sufc[i] = 1;

	for (int k = 1 ; k <= N ; k ++) {
		M = INT_MIN;
		for (auto i: rr) {
			for (auto j: cc) {
				if (row[i]+col[j]-a[i][j] > M) {
					M = row[i]+col[j]-a[i][j];
					r = i, c = j;
				}
			}
		}
//		cout << M << " ";
		for (int q = 1 ; q <= N ; q ++) col[q] -= a[r][q], row[q] -= a[q][c];
		rr.erase(r), cc.erase(c);
		sufr[r] = 0, sufc[c] = 0;
		int ansr = 1, ansc = 1;
		for (int q = 1 ; q < r ; q ++) ansr += sufr[q];
		for (int q = 1 ; q < c ; q ++) ansc += sufc[q];
//		printf("%d %d\n",r,c);
		printf("%d %d\n",ansr,ansc);
	}
			 
} 

/**

3
1 0 0
0 10 10
0 10 10

2 2
1 2
1 1

**/ 

#include<bits/stdc++.h>
using namespace std;

int T,N,M,ANS,a,b,c;
vector<int> v;
map<int, int> s, mul;

int main()
{
	scanf("%d",&T);
	while (T --) {
		scanf("%d",&N);
		M = 0, ANS = INT_MAX;
		s.clear(), mul.clear(), v.clear(); 
		for (int i = 1 ; i <= N ; i ++) {
			scanf("%d%d%d",&a,&b,&c);
			if (c == 0) {
				v.push_back(b);
				s[b] = a;
				mul[b] = 0;
			} else {
				v.pop_back();
				int k = a - s[b] - mul[b];
				if (v.size()) mul[v[v.size()-1]] += a - s[b];
//				cout << b << "  " << k << "\n";
				if (k > M || (k == M && ANS > b)) M = k, ANS = b;
//				for (auto j: v) mul[j] += k;
			}
		}
		printf("%d\n", ANS);
	}
} 

/**

1
8
1 1 0
5 2 0
10 3 0
20 3 1
25 4 0 
40 4 1
1000 2 1
2000 1 1

1

**/ 

#include<bits/stdc++.h>
using namespace std;

int T,N,M,CNT,CNTT,sx,sy;
set<pair<int, int>> s;
string ss;
char m[51][51]; 
pair<int, int> p[10];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

struct sss{
	int x, y, path;
	sss(int xx, int yy, int pathh): x(xx),y(yy),path(pathh) {}
};

int minp(int x, int y)  // FIND DIS_MIN BOX_INDEX
{
	int dis = INT_MAX, ANS = -1;
	for (int i = 0 ; i <= CNT ; i ++) {
		int d = abs(p[i].first-x) + abs(p[i].second-y);
		if (d < dis) dis = d, ANS = i;
	}
	return ANS;
}

int bfs(int x, int y, int ex, int ey) // BFS FIND MIN_DIS
{
	int path = 0;
	queue<sss> q;
	q.push(sss(x, y, 0));
	
	while (q.size()) {
		sss pp = q.front();
		q.pop();
		
		if (pp.x == ex && pp.y == ey) return pp.path;
		
		for (int i = 0 ; i < 4 ; i ++) {
			int xx = pp.x + dx[i];
			int yy = pp.y + dy[i];
			if (xx >= 0 && xx < N && yy >= 0 && yy < N && m[xx][yy] != '#') {
				q.push(sss(xx, yy, pp.path+1)); 
			}
		}
	}
	
	return -1;
}

int main()
{
	cin >> T;
	while (T --) {
		
		cin >> N >> M;
		CNT = -1;
		s.clear();
		
		for (int i = 0 ; i < 10 ; i ++) p[i] = pair<int, int>(INT_MAX, INT_MAX);
		
		for (int i = 0 ; i < N ; i ++) {
			cin >> ss;
			for (int j = 0 ; j < M ; j ++) {
				m[i][j] = ss[j];
				if (ss[j] == '*') sx = i, sy = j;
				else if (ss[j]>='0' && ss[j]<='9') {
					CNT = max(CNT, ss[j]-'0');
					p[ss[j]-'0'] = pair<int, int>(i, j);
				}
			}
		}    // READ FINISHED
		
		int ANS = 0;
		CNTT = CNT;
		s.insert(pair<int, int>(sx, sy));
		
		while (1) {
			
			int index = minp(sx, sy);
			bool f = false;
			int a = bfs(sx, sy, p[index].first, p[index].second);
			if (a == -1) {
				cout << -1 << "\n";
				break;
			}
			
			for (int i = 0 ; i < 4 ; i ++) {
				int xx = sx + dx[i];
				int yy = sy + dy[i];
				if (xx >=0 && xx < N && yy >= 0 && yy < M && m[xx][yy] != '#') {
					
					int b = bfs(xx, yy, p[index].first, p[index].second);
					if (b<a) {
						if (s.count((pair<int, int>(xx, yy))) > 0) {
							f = true;
							break;
						}
						s.insert((pair<int, int>(xx, yy)));
						sx = xx, sy = yy;
					}
					
					char w = m[sx][sy];
					if (w >= '0' || w <= '9') {
						p[w-'0'] = pair<int, int>(INT_MAX, INT_MAX);
						m[sx][sy] = '.';
						CNTT --;
						s.clear();
					}
				}
			}
			
			if (f) {
				cout << -1 << "\n";
				break;
			}
			ANS ++;	
			
			if (CNTT == 0) {
				cout << ANS << "\n";
				break;
			}
			
		}
		
	}
} 

/**

3
5 5
0...1
.#.#.
..*..
.#.#.
2...3
5 5
0...1
.#.#.
..*.#
.#.#.
2.#.3
5 5
....1
.####
..*..
####.
0....


16
-1
-1

**/