8972: String Problem

Little L raised a question:

Given a string S of length n containing only lowercase letters.

You need to select several non-empty substrings of S so that they are disjoint pairwise, and each substring is a palindrome.

Assuming you have selected K substrings(�1,�2...��s1,s2...sk) that satisfy the above conditions, your score is the sum of the lengths of all substrings minus K. It is ∑�=1����(��)−�∑i=1Klen(si)−K

But Little L is a dedicated person, and to increase difficulty, Little L requires that each palindrome string contain at most one kind of letter

Little L wants you to find the maximum score.

A positive integer $T$ in the first line represents the number of test groups, for each group of test data:

The only line contains a string of length $n$ which containing only lowercase letters.

�≤20,∑�≤106T≤20,∑n≤106