A partition of a string is a set of one or more non-overlapping non-empty substrings of
(call them
), such that
is their concatenation:
.
We call these substrings "chunks" and define the length of such a partition to be the
number of chunks,
.
We can represent the partition of a string by writing each chunk in parentheses. For
example, the string "decode" can be partitioned as or
or
or
or
or a number of other ways.
A partition is palindromic if its chunks form a palindrome when we consider each
chunk as an atomic unit. For example, the only palindromic partitions of "decode"
are and
. This also illustrates that every word has a trivial
palindromic partition of length one.
Your task is to compute the maximal possible number of chunks in palindromic partition.
Input
The input starts with the number of test cases in the first line. The following
lines
describe individual test cases consisting of a single word
, containing only lowercase
letters of the English alphabet. There are no spaces in the input.
Output
For every test case, output a single number: the length of the longest palindromic partition
of the input word .
Constraints
Let us denote the length of the input string with
.
Subtask 1 (15%)
Subtask 2 (20%)
Subtask 3 (25%)
Subtask 4 (40%)
- no additional constraints
Sample Input 1
4
bonobo
deleted
racecar
racecars
Sample Output 1
3
5
7
1
Comments