万圣节服饰

Description

Gappu 有一个非常忙碌的周末，因为万圣节到了，他要参加许多化装舞会，不同类型的化装舞会要穿上不同的服饰，当然相同类型的化装舞会就穿一样的服饰。Gappu有一个坏习惯，脱下的服饰就扔了不再使用。Gappu决定服饰可以套着穿，即一件服饰外面再套上一件服饰。Gappu最近有点拮据，请你帮助他算算最少需要多少服饰。

Input

输入第一行一个T（≤200），表示测试组数： 每组第一行一个N（1≤N≤100）,表示化装舞会场数； 第二行N个整数Ci（1≤Ci≤100）表示化装舞会类型，按参加的先后顺序。

Output

每组数据：先输出“Case X: ”，其中X表示测试组号，后面是所需最少的服饰数。

Sample Input

2 4 1 2 1 2 7 1 2 1 1 3 2 1

Sample Output

Case 1: 3 Case 2: 4

题解

区间dp。 设f[i][j]为第i个舞会到第j个舞会需要多少件衣服。 首先f[i][i] = 1。 如果a[i] = a[j]，那么f[i][j] = f[i][j-1]。 然后枚举k，f[i][j] = min(f[i][k], f[k+1][j])，(i <= k < j)。