Description

You are given a string containing only lowercase letters. You need to partition it into as many blocks as possible, such that these blocks form a palindrome string.

For example, for the string abcab, partitioning it into ab c ab or just abcab is a valid way to make the blocks form a palindrome, while abc ab is not.

Input Format

The first line contains an integer $T$, indicating the number of test cases.

The next $T$ lines each contain a string, representing the string you need to process. It is guaranteed that the string contains only lowercase letters.

Output Format

Output $T$ lines. For each input string, output one line containing an integer $x$, indicating the maximum number of blocks the string can be partitioned into, such that these blocks form a palindrome.

4
bonobo
deleted
racecar
racecars

3
5
7
1

Hint

For $100\%$ of the testdata, $1 \le T \le 10$. Let $L$ be the length of a single string, then $1 \le L \le 10^6$.

Translated by ChatGPT 5