Comet OJ

C1733 [CEOI2017Day2] Palindromic Partitions

内存限制：128 MB 时间限制：10000 ms

题目描述

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,a_3,...,a_d)$, such that $s$ is their concatenation: $s = a_1+a_2+a_3+...+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.

输入格式

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.

输出

For every test case output a single number: the length of the longest palindromic partition of the input word $s$.

样例

样例输入 1

4
bonobo
deleted
racecar
racecars

样例输出 1

3
5
7
1

提示

Constraints

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

  • $1≤ t ≤10$
  • $1≤ n ≤10^6$

Subtask 1 (15 points)

  • $n ≤30$

Subtask 2 (20 points)

  • $n ≤300$

Subtask 3 (25 points)

  • $n ≤10000$

Subtask 4 (40 points)

  • no additional constraints