Qua_cau

Qua Cầu
Có 1 số cây cầu làm bằng gỗ. Trải qua 1 thời gian,những  cây cầu trở nên hư hại và xuất hiện những lỗ thủng trên đó. Được biết những cây cầu đó luôn có độ rộng M = 5(bước đi) và độ dài trong khoảng3

Công việc:

Có 1 người luôn luôn đứng giữa ở 1 phía của cây cầu. Nhiệm vụ của bạn là phải đưa người đó qua được cầu với số đồng xu nhặt được là lớn nhất. Được biết trên cầu có 1 số đồng xu bị đánh rơi và người đó chỉ có thể đi thẳng, đi chéo trái hoặc đi chéo phải. Ngoài ra người đó có mang 1 tấm ván. Nó có thể vá được 1 lỗ thủng trên cầu giúp người đó có thể đi qua được.

Lưu ý : không có nhiều hơn 1 đồng xu tại 1 địa điểm.

 

Input

Dòng đầu tiên là số lượng trường hợp thử nghiệm.

Dòng thứ 2 chiều dài của cây cầu (N).

N dòng tiếp theo mô tả cây cầu theo ma trận 2 chiều. Trong đó: ‘0’ là có thể đi được, ‘1’ là có đồng xu(có thể đi được)và ‘2’ là lỗ thủng.

 

Output

In theo định dạng  “#test_case” và số đồng xu nhiều nhất có thể khi qua đươc cầu.

Nếu không thể qua cầu in ra  -1.











Sample



Input



3



7



1 2 0 1 0



0 0 2 0 1



0 1 0 2 1



1 0 0 0 1



0 0 0 2 2



2 0 1 0 1



0 1 2 2 0



10



2 2 2 2 0



1 2 0 0 2



0 2 0 0 0



2 2 0 2 2



0 2 2 2 0



0 0 0 0 0



1 0 0 0 2



0 0 0 0 0



2 2 0 2 1



0 2 2 2 0



9



0 2 1 1 2



0 2 2 2 2



2 2 2 1 0



0 0 2 0 2



0 2 2 1 0



1 0 2 2 2



2 2 0 2 0



2 2 2 0 2



0 0 2 0 0



 



Output



#1 6



#2 -1



#3 0

=============================

#include <iostream>
using namespace std;
int dx[] = {-1,-1,-1};
int dy[] = {-1,0,1};
int N, xu;
int a[15][6], visit[15][6];

void nhap(){
	cin >> N;
	for(int i=0; i<N; i++){
		for(int j=0; j<5; j++){
			cin >> a[i][j];
			visit[i][j] = 0;
		}
	}
}
void backtrack(int r, int c, int coin, int hp){
	for(int i=0; i<3; i++){
		int nx = r + dx[i];
		int ny = c + dy[i];
		if(nx>=0 && nx<N && ny>=0 && ny<5){
			if(a[nx][ny] == 0){
				backtrack(nx,ny,coin,hp);
			}
			if(a[nx][ny] == 1){
				backtrack(nx,ny,coin+1,hp);
			}
			if(a[nx][ny] == 2 && hp>0){
				backtrack(nx,ny,coin,hp-1);
			}
		}
	}
	if(r==0){
		if(xu<coin)	xu = coin;
		return;
	}

}

int main(){
	freopen("INP.txt","r",stdin);
	int T; cin >> T;
	for(int tc=1; tc<=T; tc++){
		nhap();
		xu = -1;
		for(int i=1; i<4; i++){
			if(a[N-1][i] == 0){
				backtrack(N-1, i, 0, 1);
			}
			if(a[N-1][i] == 1){
				backtrack(N-1, i, 1, 1);
			}
			if(a[N-1][i] == 2){
				backtrack(N-1, i, 0, 0);
			}
		}
		cout << '#' << tc << " " << xu << endl;
	}
	return 0;
}