C. Нестабильная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана строка $$$s$$$, состоящая из символов 0, 1 и ?.

Назовем строку нестабильной, если она состоит из символов 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$$$.

Пример
Входные данные
3
0?10
???
?10??1100
Выходные данные
8
6
25