CF1535C.Unstable String

You are given a string $s$ consisting of the characters 0, 1, and ?.

Let's call a string unstable if it consists of the characters 0 and 1 and any two adjacent characters are different (i. e. it has the form 010101... or 101010...).

Let's call a string beautiful if it consists of the characters 0, 1, and ?, and you can replace the characters ? to 0 or 1 (for each character, the choice is independent), so that the string becomes unstable.

For example, the strings 0??10, 0, and ??? are beautiful, and the strings 00 and ?1??1 are not.

Calculate the number of beautiful contiguous substrings of the string $s$.

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

我们称一个不稳定字符串为：仅由字符 0 和 1 构成，且任意两个相邻字符均不相同（即形如 010101... 或 101010...）。

我们称一个优美字符串为：仅由字符 0、1 和 ? 构成，且你可以将每个 ? 独立地替换为 0 或 1，使得最终得到的字符串是不稳定的。

例如，字符串 0??10、0 和 ??? 是优美的，而字符串 00 和 ?1??1 不是优美的。

请计算字符串 $s$ 中优美连续子串的数量。

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

The first and only line of each test case contains the string $s$ ($1 \le |s| \le 2 \cdot 10^5$) consisting of characters 0, 1, and ?.

It is guaranteed that the sum of the string lengths over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例仅有一行，包含字符串 $s$（$1 \le |s| \le 2 \cdot 10^5$），该字符串由字符 0、1 和 ? 组成。

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

For each test case, output a single integer — the number of beautiful substrings of the string $s$.

对于每个测试用例，输出一个整数——字符串 $s$ 中优美子串的个数。