시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 128 MB116504544.118%

문제

A partition of a string s is a set of one or more non-overlapping non-empty substrings of s (call them a1, a2, a3, . . . , ad), such that s is their concatenation: s = a1 +a2 +a3 +. . .+ad. 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 testcase output a single number: the length of the longest palindromic partition of the input word s.

제한

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

• 1 ≤ t ≤ 10
• 1 ≤ n ≤ 106

번호 배점 제한
1 15

n ≤ 30

2 20

n ≤ 300

3 25

n ≤ 10 000

4 40

예제 입력 1

4
bonobo
deleted
racecar
racecars


예제 출력 1

3
5
7
1


채점 및 기타 정보

• 예제는 채점하지 않는다.