说明

时间限制：1 Sec 内存限制：256 MB 输入文件：aba.in 输出文件：aba.out

小明很喜欢“阿巴”这个词的发音，所以当佳佳给了他一个全部由小写字母 a 和 b 组成的字符串 $s$ 时，他忍不住要从中寻找发音为“阿巴”和“巴”的子串。

他把只包含 a 和 b ，且任意相邻两个字母都不同的字符串叫做“阿巴串”。

但是佳佳想增加一点点难度。她给小明的字符串里除了 a 和 b 之外，还有可能包含问号 ?。每一个问号 ? 都可以替换为 a 或 b。

在小明看来，如果一个字符串只包含 a、b 和 ?，并且把每个 ? 独立地替换为 a 或 b，使得整个字符串变为阿巴串，那这个字符串就是“准阿巴串”。

例如，字符串 a??ba、a、??? 是准阿巴串，而 aa 和 ?b??b 不是。

请计算字符串 $s$ 中，有多个子串是准阿巴串。

注：从字符串 $s$ 的开头向后和结尾向前任意挑选连续的 $0$ 个或多个字符并删除后，留下的部分叫做 $s$ 的子串。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来有 $t$ 行，第 $i$ 行为第 $i$ 组询问，为一个仅包含 a、b、? 的字符串 $s$。

输出格式

$t$ 行，第 $i$ 行为对第 $i$ 组询问的回答，为一个整数，表示输入的字符串中有多少个子串是准阿巴串。

样例

样例 1

3
a?ba
???
?ba??bbaa

8
6
25

样例说明：

在第 $1$ 组询问中，单个字符都是准阿巴串，这样就有 $4$ 个，然后 a?、?b、ba、?ba 都是准阿巴串，共 $8$ 个。

在第 $2$ 组询问中，长度为 $1$、$2$、$3$ 的所有子串都是准阿巴串，共 $6$ 个。

数据范围

$1 \le t \le 10^4$

令 $|s|$ 表示字符串 $s$ 的长度，有 $1 \le |s| \le 2 \times 10^5$

题目保证所有询问中的 $s$ 之和不超过 $2 \times 10^5$