collect_max_coins_Samsung

#include <iostream>
using namespace std;

int n;
int mat[15][15];
int ans;

bool valid(int x, int y){
    if(x>=0 && x<n && y>=0 && y<5)
        return true;
    return false;
}

void solve(int r, int c, int power, bool magic, int score){
    //getting max every time
    ans=max(ans,score);

    //base case
    if(r==0){
        ans=max(ans,score);
        return;
    }
    int dy[]={-1,0,1};
    for(int i=0; i<3; i++){
        int x = r-1;
        int y = c+dy[i];

        if(valid(x,y)){
            if(mat[x][y]==2){
                if(magic)
                    solve(x,y,5,0,score);

                if(score>0)
                    solve(x,y,power-1,magic,score-1);

                if(power>0)
                    solve(x,y,power-1,0,score);

                if(score==0 && power<=0 && magic==0){
                    ans=max(ans,score);
                    return;
                }
            }
            if(mat[x][y]==1) solve(x,y,power-1,magic,score+1);
            if(mat[x][y]==0) solve(x,y,power-1,magic,score);
        }
    }
}

int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>n;

        for(int i=0; i<n; i++)
            for(int j=0; j<5; j++)
                cin>>mat[i][j];

        ans=-1;
        solve(n,2,0,1,0);
        if(ans==0) cout<<-1<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}