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\)