[CEOI2017] Palindromic Partitions

题目描述

给出一个只包含小写字母字符串,要求你将它划分成尽可能多的小块,使得这些小块构成回文串。 例如:对于字符串 ``abcab``,将他分成 ``ab`` ``c`` ``ab`` 或者 ``abcab`` 就是构成回文串的划分方法,``abc`` ``ab`` 则不是。

输入输出格式

输入格式


第一行输入一个整数 $T$ 表示数据组数。 接下来的 $T$ 行,每行输入一个字符串,代表你需要处理的字符串,保证该字符串只包含小写字母。

输出格式


输出 $T$ 行,对于每个输入的字符串,输出一行包含一个整数 $x$,表示该字符串最多能分解成 $x$ 个小块,使得这些小块构成回文串。

输入输出样例

输入样例 #1

4
bonobo
deleted
racecar
racecars

输出样例 #1

3
5
7
1

说明

对于 $100\%$ 的数据,有 $1\le T\le 10$。设 $L$ 为单个字符串的长度,则 $1\le L\le 10^6$​​。