题目描述

多多有一个长度为n的字符串, 这个字符串仅由26个小写字母组成。

多多可以对这个字符串进行多次操作, 每次操作可以把该字符串中一段连续的回文子串删除(单个字符也属于回文串), 删除后剩下的串会拼在一起。

请问最少需要多少次操作可以将这个字符串删光。

输入描述

第一行, 包含一个正整数 T(1 <= T <= 20) 代表测试数据的组数。

对于每组测试数据, 仅有一行, 代表这个字符串，长度为n。

(1 <= n <= 500)

保证Σn不超过3000

注：由于本题数据较大，python通过不了，请使用java和c++。

输出描述

对于每组数据输出一行整数, 代表多多在进行最少多少次操作后, 可以将这个字符串删光。

输入示例

3
mwapd
tvuvv
yxxmi

输出示例

5
3
4

提示信息

第一个字符串： 每次删除一个，共5次；

第二个字符串：

第一步: 删除u, 此时剩下tvvv

第二步: 删除vvv, 此时剩下t

第三步: 删除t

共3次；

第三个字符串：需要4次。

时间限制：c/c++：1s；java：5s；其他语言：10s。