You are given a string $S$ consisting of lowercase English letters. Your task is to find the maximum number of palindromic subsequences that can be created from the given string. Each palindromic subsequence must have a length greater than 1, and each element of the string can be part of atmost one palindromic subsequence.

We'll call non-empty string $S[p_1p_2 \cdots p_k] = S_{p_1}S_{p_2} \cdots S_{p_k} (1 \leq  p1 \lt p2 \lt \cdots \lt p_k \leq |S|)$ subsequence of string $S = S_1S_2 \cdots S_{|s|}$, where |S| is the length of string S. For example, strings "abcb", "cb" and "abacaba" are subsequences of string "abacaba".

Input format

• The first line of input contains an integer $T$ denoting the number of test cases.
• Each test case consists the string $S$.

Output format

For each test case, print the maximum number of palindromic subsequences you can create in a separate line.

Constraints

$1\le T \le 100 \\ 2 \leq |S| \le 10^4$