P4656 [CEOI 2017] Palindromic Partitions

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.

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 $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.

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