A partition of a string $s$ is a set of one or more non-overlapping non-empty substrings of $s$ (call them $a_1,a_2,\dots ,a_d$), such that $s$ is their concatenation: $s=a_1+a_2+\cdots +a_d$. We call these substrings "chunks" and define the length of such a partition to be the number of chunks, $d$.

We can represent the partition of a string by writing each chunk in parentheses. For example, the string "decode" can be partitioned as $(d)(ec)(ode)$ or $(d)(e)(c)(od)(e)$ or $(decod)(e)$ or $(decode)$ or $(de)(code)$ 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 $(de)(co)(de)$ and $(decode)$. 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 $t$ in the first line. The following $t$ lines describe individual test cases consisting of a single word $s$, 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 $s$.

Constraints

Let us denote the length of the input string $s$ with $n$.

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

Subtask 1 (15%)

• $n\le 30$

Subtask 2 (20%)

• $n\le 300$

Subtask 3 (25%)

• $n\le 10000$

Subtask 4 (40%)

• no additional constraints

Sample Input 1

4
bonobo
deleted
racecar
racecars

Sample Output 1

3
5
7
1