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 $(s_1,s_2...s_k)$ that satisfy the above conditions, your score is the sum of the lengths of all substrings minus $K$. It is $∑_{i=1}^Klen(s_i)−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.

$T≤20,∑n≤10^6$

For each test data, print a number representing the maximum score.