← 返回题目列表

Codeforces · 1535/C

C. 字符串不稳定

中文机器翻译题面 查看原题

给定一个由字符 0、1 和 ? 组成的字符串 $$$s$$$。

如果一个字符串由字符 0 和 1 组成,并且任何两个相邻字符不同(即它的形式为 010101... 或 101010...),我们称该字符串不稳定。

如果一个字符串由字符 0、1 和 ? 组成,并且您可以替换字符 ?,那么我们称该字符串为漂亮字符串。为0或1(对于每个字符,选择是独立的),从而使字符串变得不稳定。

例如,字符串 0??10、0 和 ???很漂亮,而字符串 00 和 ?1??1 则不然。

计算字符串$$$s$$$的漂亮连续子串的数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$),由字符 0、1 和 ? 组成。

保证所有测试用例的字符串长度总和不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——字符串 $$$s$$$ 的漂亮子串的数量。

示例

输入 #1

3
0?10
???
?10??1100

输出 #1

8
6
25