给定一个由字符 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