#1039. 「2020 多校联考·平邑」字符串

内存限制:512 MiB 时间限制:4000 ms 输入文件:string.in 输出文件:string.out
题目类型:传统 评测方式:文本比较
上传者: Handwer

题目描述

有一天,一个富有的商人找到了你。他给了你很多很多金币,让你帮助他来完成任务。

他首先给出了一个字符串,你每次可以花费一个金币来覆盖其中的一个回文串的所有字符。

而商人交给你的任务是让整个字符串的每个字符至少被覆盖一遍。尽可能的省下来金币去买自己喜欢的东西。

所以你就想找到一种花费最少的方案覆盖整个字符串。我相信聪明的你肯定能找到,并且可以求出来最少的花费。

输入格式

第一行包含一个整数 t ,表示有 t 组数据。 接下来 t 行每行一个字符串 s s 的长度不超过 10^6

输出格式

对于每组数据输出一个整数,表示覆盖住整个字符串需要的最少花费。

样例

样例输入

1
aabcbaabbcbbaxx

样例输出

3

数据范围与提示

对于 10\% 的数据, s 的长度不超过 100

对于 20\% 的数据, s 的长度不超过 1000

对于 100\% 的数据, 0 \leq t \leq 32 s 的长度不超过 10^6