B. 字符串删除

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

给定一个长度为 $n$ 的字符串 $S$ ，你必须从中选择一个连续子串，将其删除。删除后剩余的子串长度不能小于 $2$ ，且剩余子串的字符不能全部相同。问合法删除方式的方案数。

第一行输入一个正整数 $T$ ，表示测试样例组数。对于每组数据：输入一行，包含一个字符串 $S$ 。 $(1\le T\le 10^5,2\le |S|\le 10^5)$ 。

数据保证 $S_i$ 为小写英文字母。且所有字符串长度总和不超过 $2\times 10^5$ 。

输出一个正整数，为合法删除的总方案数。

3
hack
hhaacckk
abcdefgghiaa

7
31
72

新生赛验题