Problem Description

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 $\sum_{i=1}^{K} len(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.

Input

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 \leq 20, \sum n \leq 10^6$

Output

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

2
etxabaxtezwkdwokdbbb
aaaaa

2
4