String Problem

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.

Sample Input

2
etxabaxtezwkdwokdbbb
aaaaa

Sample Output

2
4

Source

2023“钉耙编程”中国大学生算法设计超级联赛（2）