Untitled

#include <iostream>
#define MAXN 13

using namespace std;

int N, ans;
int map[MAXN][5];
int dy[3] = {-1, 0, 1};

void input()
{

	cin >> N;
	for(int j = 0; j < 5; j++){
		map[N][j] = 0;
	}
	for(int i = 0; i < N; i++){
		for(int j = 0; j < 5; j++){
			cin >> map[i][j];
		}
	}
}

void backTrack(int row, int col, int coin, int bomb, bool checkBomb)
{
	if(col < 0 || col >= 5)
		return;

	if(map[row][col] == 2 && bomb <= 0){
		if(coin <= 0)
			return;
		else
			coin--;
	}
	else if(map[row][col] == 1){
		coin += map[row][col];
	}

	if(row < 0){
		if(coin > ans)
			ans = coin;
		return;
	}

	bomb--;

	backTrack(row - 1, col - 1, coin, bomb, checkBomb);
	if(checkBomb){
		backTrack(row - 1, col - 1, coin, 5, false);
	}

	backTrack(row - 1, col, coin, bomb, checkBomb);
	if(checkBomb){
		backTrack(row - 1, col, coin, 5, false);
	}

	backTrack(row - 1, col+1, coin, bomb, checkBomb);
	if(checkBomb){
		backTrack(row - 1, col+1, coin, 5, false);
	}

}

int main()
{
	freopen("input.txt", "r", stdin);
	int T; 
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		input();
		ans = -1;
		backTrack(N, 2, 0, 0, true);
		cout << ans << endl;
	}
	return 0;
}