/***********Template Starts Here***********/
#include <bits/stdc++.h>

#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((vlong)(x).size())
#define NORM(x) if(x>=mod)x-=mod;

using namespace std;

typedef long long vlong;

const vlong inf = 2147383647;

/***********Template Ends Here***********/
int arr[1010];

vlong LIS[1010], LDS[1010], pwr[1010], cum[1010];

vlong memo[1010][1010];
int knuth[1010][1010], cc = 1;
int done[1010][1010];

vlong dp ( int st, int en ) {
    if ( st == en ) {
        knuth[st][en] = st;
        return 0;
    }
    if ( done[st][en] == cc ) return memo[st][en];

    vlong res = inf * inf;

    dp ( st, en - 1 ); ///First calculate this
    dp ( st + 1, en ); ///First calculate this

    int kst = knuth[st][en-1]; ///Knuth's Optimization
    int ken = knuth[st+1][en]; ///Knuth's Optimization
    if ( ken == en ) ken--;

    FOR ( iron, kst, ken ) {
        vlong cost = cum[en] - cum[st-1];
        vlong tres = cost + dp ( st, iron ) + dp ( iron + 1, en );
        if ( tres <= res ) {
            res = tres;
            knuth[st][en] = iron;
        }
    }

    done[st][en] = cc;
    return memo[st][en] = res;
}


int main () {
    #ifdef forthright48
    freopen ( "input.txt", "r", stdin );
    //freopen ( "output.txt", "w", stdout );
    #endif // forthright48

    int kase, cnt = 0;
    scanf ( "%d", &kase );

    while ( kase-- ) {
        int n;
        scanf ( "%d", &n );

        FOR(iron,0,n-1){
            scanf ( "%d", &arr[iron] );
        }

        FOR(iron,0,n-1){
            LIS[iron] = 1;
            LDS[iron] = 1;
        }


        ///Find LIS from front
        FOR(iron,0,n-1){
            FOR(joker,iron+1,n-1){
                if ( arr[iron] < arr[joker] && LIS[iron] + 1 > LIS[joker] ) {
                    LIS[joker] = LIS[iron] + 1;
                }
            }
        }
        ///Find LIS from back
        ROF(iron,0,n-1){
            ROF(joker,0,iron-1){
                if ( arr[iron] < arr[joker] && LDS[iron] + 1 > LDS[joker] ) {
                    LDS[joker] = LDS[iron] + 1;
                }
            }
        }

        ///Calculate PWR. Made it 1-indexed
        FOR(iron,0,n-1){
            pwr[iron+1] = LIS[iron] + LDS[iron] - 1;
            cum[iron+1] = pwr[iron+1] + cum[iron];
        }

        ///Now calculate DP
        cc++;
        vlong res = dp ( 1, n );

        printf ( "Case %d: %lld\n", ++cnt, res );
    }

    return 0;
}