UVA 10559 / MCM - DP

/***
 created: 2022-07-22-21.52.17
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll a[1000],n;

ll dp[202][202][205];

ll solve(ll s,ll e,ll cnt)
{
    if(s>e) return 0;

    if(dp[s][e][cnt]!=-1) return dp[s][e][cnt];

    ll ans = cnt*cnt + solve(s+1,e,1);

    for(ll i=s+1;i<=e;i++)
    {
        if(a[s]==a[i])
        {
            ans=max(ans, solve(s+1,i-1,1) +  solve(i,e,cnt+1));
        }
    }

    return dp[s][e][cnt]=ans;

}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    test
    {
        ll i,j,k,l;

        cin>>n;

        for(i=0;i<n;i++) cin>>a[i];

        memset(dp,-1,sizeof dp);

        cout<<"Case "<<cs<<": "<<solve(0,n-1,1)<<nl;
    }


    get_lost_idiot;
}