#include <iostream>
using namespace std;
#include <cstring>

int N;
int arr[100][100];
int dp[100][100];

int jump(int y, int x) {
	if (y >= N || x >= N) return 0;
	if (y == N - 1 && x == N - 1) return 1;

	int& ret = dp[y][x];
	if (ret != -1) return ret;

	int jumpsize = arr[y][x];
	return ret = (jump(y + jumpsize, x) || jump(y, x + jumpsize));
}

int main()
{
	int C; cin >> C;
	while (C--) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> arr[i][j];
			}
		}

		memset(dp, -1, sizeof(dp));

		if (jump(0, 0) == 1) cout << "YES\n";
		else cout << "NO\n";

	}
}

#include <iostream>
using namespace std;
#include <cstring>

int N;
string S;
string W;
string arr[50];
int dp[101][101];

bool match_bf(const string& w, const string& s) {
	int pos = 0;
	while (pos < w.size() && pos < s.size() && (w[pos] == '?' || w[pos] == s[pos]))
		pos++;
	if (pos == w.size()) return pos == s.size();
	if (w[pos] == '*') {
		for (int skip = 0; pos+skip <= s.size(); ++skip) {
			if (match_bf(w.substr(pos + 1), s.substr(pos + skip)))
				return true;
		}
	}
	return false;
}

int match_dp(int w, int s) {

	int& ret = dp[w][s];
	if (ret != -1) return ret;

	while (s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s]) ){
		w++; s++;
	}

	if (w == W.size()) return ret = (s == S.size());
	if (W[w] == '*') {
		for (int skip = 0; skip + s <= S.size(); ++skip)
			if (match_dp(w + 1, s + skip)) return ret = 1;
	}

	return ret = 0;
}

int match_dp2(int w, int s) {
	int& ret = dp[w][s];
	if (ret != -1) return ret;

	while (s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s])) {
		return ret = match_dp2(w + 1, s + 1);
	}

	if (w == W.size()) return ret = (s == S.size());

	if (W[w] == '*') {
		if (match_dp2(w + 1, s) || s < S.size() && match_dp2(w, s + 1))
			return ret = 1;
	}

	return ret = 0;
}


int main()
{
	int C; cin >> C;
	while (C--) {
		cin >> W; cin >> N;
		for (int i = 0; i < N; i++) {
			cin >> arr[i];
		}

    vector<string> ans;

		for (int i = 0; i < N; i++) {
			memset(dp, -1, sizeof(dp));
			S = arr[i];
			if (match_dp2(0, 0) == 1) ans.push_back(arr[i]);
		}

		sort(ans.begin(), ans.end());
		for (string str : ans) {
			cout << str << endl;
		}

	}

}

#include <iostream>
using namespace std;
#include <cstring>
#include <algorithm>

int N;
int arr[100][101];
int dp[100][101];

int pathsum(int y, int x) {
	if (y == N - 1) return arr[y][x];

	int& ret = dp[y][x];
	if (ret != -1)return ret;

	return ret = max(pathsum(y + 1, x), pathsum(y+1, x + 1)) + arr[y][x];
}

int main()
{
	int C; cin >> C;
	while (C--) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= i; j++) {
				cin >> arr[i][j];
			}
		}

		memset(dp, -1, sizeof(dp));

		cout << pathsum(0, 0) << endl;


	}

}