1004 monkey banana

#include<iostream>
#include<cstring>
#include<cstdio>

#define MAX 220
#define MAXI 110
#define inf 999
#define mem(x,y) memset(x,y,sizeof(x))
#define scan scanf("%lld",&mat[i][j]);
#define sn(n) scanf("%lld",&n);
#define pf(n) printf("Case %lld: %lld\n",cased,n);
#define ull  long long
using namespace std;
ull mat[MAX][MAXI],n,r,c,cased=1,test;
ull dp[MAX][MAXI];
ull call(ull i,ull j)
{
    if(i>=0 && i<r and j>=0 and j<c) //if still inside the array
    {
        if(dp[i][j]!=-1) return dp[i][j];
        //if(mat[i][j]==-1) return 0;
        //ull ret=-10;
        ull ret =-100;
                //try to move to 3 direction,also add current cell's poull

        ret=max(ret,call(i+1,j)+mat[i][j]);
        ret=max(ret,call(i+1,j-1)+mat[i][j]);
        ret=max(ret,call(i+1,j+1)+mat[i][j]);
        return dp[i][j]=ret;
    }
    else return 0; //if outside the array
}



int main()
{//cout<<-inf;

    sn(test)
    while(test--){
   sn(n)
    mem(dp,-1);
    mem(mat,-1);

    for(ull i = 0;i<2*n-1;i++)
    {
        if(i<n)
        for(ull j = 0;j<=i;j++)
        scan

        else
        for(ull j=0;j<2*n-1-i;j++)
        scan

    }
   // cout<<mat[0][0];
    r = 2*n-1;
    c = n;
    //dp[0][0] = mat[0][0];
    pf(call(0,0));
    cased++;
    }

}