## CEOI '17 P5 - Palindromic Partitions

View as PDF

Points: 15 (partial)
Time limit: 4.5s
Memory limit: 128M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

A partition of a string is a set of one or more non-overlapping non-empty substrings of (call them ), such that is their concatenation: . We call these substrings "chunks" and define the length of such a partition to be the number of chunks, .

We can represent the partition of a string by writing each chunk in parentheses. For example, the string "decode" can be partitioned as or or or or 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 and . 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 in the first line. The following lines describe individual test cases consisting of a single word , containing only lowercase letters of the English alphabet. There are no spaces in the input.

#### Output

For every testcase output a single number: the length of the longest palindromic partition of the input word .

#### Constraints

Let us denote the length of the input string with .

#### Sample Input 1

4
bonobo
deleted
racecar
racecars

#### Sample Output 1

3
5
7
1