## Azza and palindromes

Points: 50 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C++

A palindrome is any sequence of characters which reads the same backward as forward. Azza, Aya, Ala are all palindromes.

Azza likes very much inventing algorithmic puzzles to solve them in her free time. She created the following problem recently :

Let's call a partition of a string $$s$$ a set of disjoint substrings of $$s$$ $$a_i$$ that when joined together form $$s$$. $$s = \sum a_i$$ for $$i \in [1,n]$$. We'll call each string $$a_i$$ a fragment and $$n$$ the size of the partition.

A partition is called palindromic iif its fragments make a palindrome when each one is considered as a whole (i.e $$a_i = a_{n+1-i}$$).For example, consider the word magoimag. It can be split into mag + oi + mag which is a palindromic partition of size 3 (3 sub-strings).

Given a string $$s$$, find its palindromic partition of maximum size and output that size.

#### Input Specification

The input starts with a line containing $$T\leq 10$$ the number of test cases.

Each test case is given a new line that contains a single string $$s$$. The size of $$s$$ will not exceed $$10^6$$

#### Output Specification

For each test case output one integer : maximum size of the palindromic partition of $$s$$.

Scoring

\begin{array}{|c|c|c|} \hline \text{Group} & \text{Points} & \text{Constraints} \cr \hline 1 & 15 & \text{the size of $s$ is at most 30} \cr \hline 2 & 20 & \text{the size of $s$ is at most 300} \cr \hline 3 & 25 & \text{the size of $s$ is at most 10000} \cr \hline 4 & 40 & \text{No additional constraints} \cr \hline \end{array}