Palindromic Partitions

A partition of a string $s$ is a set of one or more non-overlapping non-empty substrings $a_1, a_2, \dots, a_d$ of $s$ whose concatenation is $s$, that is $s = a_1 + a_2 + \dots + a_d$. Each substring is called a chunk, and the length of the partition is the number of chunks $d$.

A partition is written by putting every chunk in parentheses. For example, the string decode can be partitioned as (d)(ec)(ode), (d)(e)(c)(od)(e), (decod)(e), (decode), (de)(code), and in many other ways.

A partition is palindromic if the sequence of chunks reads the same forwards and backwards when each chunk counts as one atomic unit. The only palindromic partitions of decode are (de)(co)(de) and (decode). The second one shows that every word has a palindromic partition of length one.

Given a word $s$, compute the largest possible length of a palindromic partition of $s$.

The first line contains the number of test cases $t$. Each of the next $t$ lines holds one test case: a single word $s$ made of lowercase letters of the English alphabet. The input contains no spaces.

For every test case print one line with the length of the longest palindromic partition of the word $s$.

Let $n$ be the length of the word $s$.

• $1 \le t \le 10$
• $1 \le n \le 10^6$