G. String Transformation
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$, consisting of lowercase Latin letters.

You can perform the following operation:

  • choose indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le |s|$$$) and a character $$$c$$$ (any lowercase Latin letter), then remove all occurrences of $$$c$$$ from the $$$l$$$-th to the $$$r$$$-th index, inclusive.

For example, if $$$s$$$ is abaabc, you can transform it into babc (by using $$$l=1$$$, $$$r=3$$$, $$$c =$$$ 'a'), abaac (by using $$$l=4$$$, $$$r=6$$$, $$$c =$$$ 'b') and abaabc (by using $$$l=2$$$, $$$r=5$$$, $$$c =$$$ 'c').

Your task is to calculate the number of different strings that can be obtained using the aforementioned operation exactly once.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains a string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), consisting of lowercase Latin letters.

Additional constraint on the input: the sum of $$$|s|$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the number of different strings that can be obtained using the aforementioned operation exactly once.

Example
Input
4
abaabc
qf
x
icpc
Output
10
3
2
6
Note

All the possible strings that can be obtained in the first example:

  • abaabc (by choosing $$$l = 1$$$, $$$r=6$$$, $$$c =$$$ 'd');
  • abaab (by choosing $$$l = 2$$$, $$$r=6$$$, $$$c =$$$ 'c');
  • abaac (by choosing $$$l = 4$$$, $$$r=6$$$, $$$c =$$$ 'b');
  • ababc (by choosing $$$l = 4$$$, $$$r=6$$$, $$$c =$$$ 'a');
  • aaabc (by choosing $$$l = 1$$$, $$$r=3$$$, $$$c =$$$ 'b');
  • baabc (by choosing $$$l = 1$$$, $$$r=2$$$, $$$c =$$$ 'a');
  • aaac (by choosing $$$l = 1$$$, $$$r=6$$$, $$$c =$$$ 'b');
  • abbc (by choosing $$$l = 3$$$, $$$r=4$$$, $$$c =$$$ 'a');
  • babc (by choosing $$$l = 1$$$, $$$r=3$$$, $$$c =$$$ 'a');
  • bbc (by choosing $$$l = 1$$$, $$$r=5$$$, $$$c =$$$ 'a').