#include<bits/stdc++.h>
using namespace std;
int f[205][205][205]; // f[l][r][cnt]: l~r合并，其中剩下cnt个与a[l],a[r]同色的最后一起合并
int T, n, m, a[205], b[205]; // a: 颜色，b: 数量
int main() {
    cin >> T;
    for (int C = 1; C <= T; C++) {
        cin >> n;
        m = 0;
        for (int i = 1; i <= n; i++) {
            int x; scanf("%d", &x);
            if (x == a[m]) b[m]++; else a[++m] = x, b[m] = 1; // 合并连续同色块
        }
        memset(f, 0xcc, sizeof(f));
        for (int i = 1; i <= m; i++)
            f[i][i][0] = b[i] * b[i], f[i][i][b[i]] = 0;
        for (int len = 2; len <= m; len++)
            for (int l = 1; l <= m - len + 1; l++) {
                int r = l + len - 1;
                for (int k = l; k < r; k++)
                    f[l][r][0] = max(f[l][r][0], f[l][k][0] + f[k + 1][r][0]);
                if (a[l] != a[r]) continue;
                int tot = b[l] + b[r]; // 控制一下循环上界，减小常数，避免超时
                for (int k = l + 1; k < r; k++)
                    if (a[k] == a[l]) tot += b[k];
                for (int cnt = b[l] + b[r]; cnt <= tot; cnt++) {
                    for (int k = l + 1; k <= r; k++)
                        if (a[l] == a[k])
                            f[l][r][cnt] = max(f[l][r][cnt], f[l + 1][k - 1][0] + f[k][r][cnt - b[l]]);
                    f[l][r][0] = max(f[l][r][0], f[l][r][cnt] + cnt * cnt);
                }
            }
        printf("Case %d: %d\n", C, f[1][m][0]);
    }
}

#include<bits/stdc++.h>
using namespace std;
long long f[9][9][9][9][16]; // 均方差等式两边平方，然后同时乘n^3，避免分数
int n, a[9][9], sum[9][9];

inline long long sqr(long long x) {
    return x * x;
}

inline int rect_sum(int u, int d, int l, int r) { // 二维子矩阵和
    return sum[d][r] - sum[d][l - 1] - sum[u - 1][r] + sum[u - 1][l - 1];
}

int main() {
    cin >> n;
    for (int i = 1; i <= 8; i++)
        for (int j = 1; j <= 8; j++) {
            scanf("%d", &a[i][j]);
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    memset(f, 0x3f, sizeof(f));
    for (int len_row = 1; len_row <= 8; len_row++)
        for (int len_col = 1; len_col <= 8; len_col++)
            for (int u = 1; u <= 8 - len_row + 1; u++) // up
                for (int l = 1; l <= 8 - len_col + 1; l++) { // left
                    int d = u + len_row - 1; // down
                    int r = l + len_col - 1; // right
                    f[u][d][l][r][1] = sqr(n * rect_sum(u, d, l, r) - sum[8][8]);
                    for (int cnt = 2; cnt <= n; cnt++) { // 分成几块
                        for (int mid = u; mid < d; mid++) { // 横着切
                            f[u][d][l][r][cnt] = min(min(
                                f[u][mid][l][r][1] + f[mid + 1][d][l][r][cnt - 1], // 切掉上面一半
                                f[u][mid][l][r][cnt - 1] + f[mid + 1][d][l][r][1] // 切掉下面一半
                            ), f[u][d][l][r][cnt]);
                        }
                        for (int mid = l; mid < r; mid++) { // 竖着切
                            f[u][d][l][r][cnt] = min(min(
                                f[u][d][l][mid][1] + f[u][d][mid + 1][r][cnt - 1], // 切掉左边一半
                                f[u][d][l][mid][cnt - 1] + f[u][d][mid + 1][r][1]
                            ), f[u][d][l][r][cnt]);
                        }
                    }
                }
    cout << setprecision(3) << fixed << sqrt(f[1][8][1][8][n] * 1.0 / (n * n * n)) << endl;
}

#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 206;
ll a[N], f[N][N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);;
    for (int i = n + 1; i <= n << 1; i++) a[i] = a[i-n];
    for (int len = 3; len <= n + 1; len++)
        for (int l = 1; l + len - 1 <= n << 1; l++) {
            int r = l + len - 1;
            for (int k = l + 1; k < r; k++)
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
        }
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, f[i][i+n]);
    cout << ans << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int f[105][105], p[105][105], n;
char a[105];

bool equals(int r, int ed, int len) { // r,ed往前len个字符是否相同
    for (int i = 0; i < len; i++)
        if (a[r - i] != a[ed - i]) return false;
    return true;
}

void print(int l, int r) {
    if (!p[l][r]) {
        for (int i = l; i <= r; i++) putchar(a[i]);
        return;
    }
    if (p[l][r] > 0) {
        print(l, p[l][r]);
        print(p[l][r] + 1, r);
    } else {
        int len = -p[l][r];
        printf("%d(", (r - l + 1) / len);
        print(l, l + len - 1);
        putchar(')');
    }
}

int main() {
    scanf("%s", a + 1);
    n = strlen(a + 1);
    memset(f, 0x3f, sizeof(f));
    for (int len = 1; len <= n; len++)
        for (int l = 1; l <= n - len + 1; l++) {
            int r = l + len - 1;
            // [l,r]拆分成两段
            if (len == 1) f[l][r] = 1;
            else for (int k = l; k < r; k++)
                if (f[l][k] + f[k + 1][r] < f[l][r]) {
                    f[l][r] = f[l][k] + f[k + 1][r];
                    p[l][r] = k;
                }
            // [l,r]]重复cnt次生成更长的字符串[l,ed]
            for (int ed = r + len, cnt = 2; ed <= n && equals(r, ed, len); ed += len, cnt++)
                if (f[l][r] + 2 + std::to_string(cnt).length() < f[l][ed]) {
                    f[l][ed] = f[l][r] + 2 + std::to_string(cnt).length();
                    p[l][ed] = -len; // 负数表示由若干个长度为len的子串循环构成
                }
        }
    print(1, n);
}

// Author: https://www.acwing.com/solution/content/12873/
#include <bits/stdc++.h>
using namespace std;

const int p = 10005;

int a[7], used[p << 1];
bool f[p];

int main()
{
    while (true)
    {
        a[0] = 0;
        for (int i = 1; i < 7; ++i) 
            cin >> a[i], a[0] += a[i] * i;

        if (a[0] == 0) break;
        if (a[0] & 1) { cout << "Can't\n"; continue; }
        memset(f, 0, sizeof f);
        a[0] >>= 1; f[0] = 1;

        for (int i = 1; i < 7; ++i)
        {
            for (int j = 0; j <= a[0]; ++j) used[j] = 0;

            for (int j = i; j <= a[0]; ++j)
                if (!f[j] && f[j - i] && used[j - i] < a[i])
                    f[j] = 1, used[j] = used[j - i] + 1;
        }

        if (f[a[0]]) cout << "Can\n";
        else cout << "Can't\n";
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int mod = 11380;
int f[31][11][11][11], L1, L2, L3, D;
int main() {
    cin >> L1 >> L2 >> L3 >> D;
    for (int i = 0; i <= D; i++) f[i][0][0][0] = 1;
    for (int i = 1; i <= D; i++)
        for (int j = 0; j <= L1; j++)
            for (int k = 0; k <= L2; k++)
                for (int l = 0; l <= L3; l++) {
                    if (j > 0) { // 第一段最外层是{}
                        for (int p = 1; p <= j; p++)
                            for (int q = 0; q <= k; q++)
                                for (int r = 0; r <= l; r++)
                                    f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][p - 1][q][r] * f[i][j - p][k - q][l - r]) % mod;
                    }
                    if (k > 0) { // 第一段最外层是[]
                        for (int q = 1; q <= k; q++)
                            for (int r = 0; r <= l; r++)
                                f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][0][q - 1][r] * f[i][j][k - q][l - r]) % mod;
                    }
                    if (l > 0) { // 第一段最外层是()
                        for (int r = 1; r <= l; r++)
                            f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][0][0][r - 1] * f[i][j][k][l - r]) % mod;
                    }
                }
    cout << (f[D][L1][L2][L3] - (D ? f[D - 1][L1][L2][L3] : 0) + mod) % mod << endl;
}

#include<bits/stdc++.h>
using namespace std;
const int T = 10000; // 平移避免负数
int a[105], n, t;
// f: 前i个数能否凑成j；g/s: true减号，false加号 
bool f[105][20005], g[105][20005], s[105];

inline bool valid(int x) { return x >= -T && x <= T;}

void sign(int i, int j) {
    if (i == 2) { s[1] = false, s[2] = true; return; }
    s[i] = g[i][j + T];
    if (s[i]) sign(i - 1, j + a[i]);
    else sign(i - 1, j - a[i]);
}

int main() {
    cin >> n >> t;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    f[2][a[1] - a[2] + T] = true;
    for (int i = 2; i < n; i++)
        for (int j = -T; j <= T; j++)
            if (f[i][j + T]) {
                if (valid(j - a[i + 1])) { // i + 1前面是负号
                    f[i + 1][j - a[i + 1] + T] = true;
                    g[i + 1][j - a[i + 1] + T] = true;
                }
                if (valid(j + a[i + 1])) { // i + 1前面是正号
                    f[i + 1][j + a[i + 1] + T] = true;
                    g[i + 1][j + a[i + 1] + T] = false;
                }
            }
    sign(n, t);
    // for (int i = 1; i <= n; i++) printf("%c", s[i] ? '-' : '+');
    // puts("");
    int merged = 0;
    // 先合并连续的加号
    // 例如 1-2-3+4+5+6-7 变成 1-2-(3-4-5-6)-7，3456合并起来
    for (int i = 2; i <= n; i++)
        if (!s[i]) printf("%d\n", i - 1 - merged), merged++;
    // 从左到右不断执行减号即可
    for (int i = 2; i <= n; i++)
        if (s[i]) puts("1");
}

#include<bits/stdc++.h>
using namespace std;
int f[82][82], n, m;
char a[82], b[82];
int preA[82][26], preB[82][26];
char ans[82];
vector<char> last[82][82];

void print(int i, int j, int len) {
    if (f[i][j] == 1) {
        ans[len] = 0;
        puts(ans);
        return;
    }
    for (int k = 0; k < last[i][j].size(); k++) {
        char ch = last[i][j][k];
        ans[len] = ch;
        print(preA[i - 1][ch - 'a'], preB[j - 1][ch - 'a'], len + 1);
    }
}

int main() {
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + m + 1);
    for (int i = 1; i <= n; i++) {
        for (int ch = 0; ch < 26; ch++) preA[i][ch] = preA[i - 1][ch];
        preA[i][a[i] - 'a'] = i;
    }
    for (int i = 1; i <= m; i++) {
        for (int ch = 0; ch < 26; ch++) preB[i][ch] = preB[i - 1][ch];
        preB[i][b[i] - 'a'] = i;
    }
    a[++n] = b[++m] = '$';
    memset(f, 0xcc, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i] == b[j]) {
                for (int ch = 'a'; ch <= 'z'; ch++) {
                    int pa = preA[i - 1][ch - 'a'];
                    int pb = preB[j - 1][ch - 'a'];
                    if (f[pa][pb] + 1 > f[i][j]) {
                        f[i][j] = f[pa][pb] + 1;
                        last[i][j].clear();
                        last[i][j].push_back(ch);
                    } else if (f[pa][pb] + 1 == f[i][j]) {
                        last[i][j].push_back(ch);
                    }
                }
            }
    print(n, m, 0);
}

#include<bits/stdc++.h>
using namespace std;
int n, a[5005], f[5005], c[5005], ans, tot;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    a[0] = 1 << 30;
    memset(f, 0xcc, sizeof(f));
    f[0] = 0, c[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if (a[j] > a[i]) {
                // f[i] = max(f[i], f[j] + 1);
                if (f[i] < f[j] + 1) f[i] = f[j] + 1, c[i] = c[j];
                else if (f[i] == f[j] + 1) c[i] += c[j];
            }
    for (int i = 1; i <= n; i++)
        if (f[i] > ans) ans = f[i], tot = c[i];
        else if (f[i] == ans) tot += c[i];
    cout << ans << ' ' << tot << endl;
}

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 106, INF = 0x7fffffff;
int n, m, a[N][N], f[N][N], d[N][N], ans[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= m - n + 1; i++) f[1][i] = a[1][i];
    for (int i = 2; i <= n; i++) {
        int k = -INF, t;
        for (int j = i; j <= m - n + i; j++) {
            if (k < f[i-1][j-1]) {
                k = f[i-1][j-1];
                t = j - 1;
            }
            f[i][j] = k + a[i][j];
            d[i][j] = t;
        }
    }
    int k = -INF, t;
    for (int i = n; i <= m; i++)
        if (k < f[n][i]) {
            k = f[n][i];
            t = i;
        }
    cout << k << endl;
    int w = n;
    while (t) {
        ans[w] = t;
        t = d[w--][t];
    }
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    puts("");
    return 0;
}