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$.


-----Input-----

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$.


-----Output-----

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


-----Examples-----

Input
3
0?10
???
?10??1100
Output
8
6
25


-----Note-----

None

Difficulty: MEDIUM
Tags: String algorithms

Sorting

Amortized analysis

Implementation

Greedy algorithms

Dynamic programming
Skill types: Dynamic programming

Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for test in range(t):
	s = input()
	n = len(s)
	ans = 0
	l = 0
	r = 0
	pr = 0
	while r < n:
		p = True
		zp = -1
		z = -1
		op = -2
		o = -2
		while r < n and p:
			if s[r] == '1':
				zp = r % 2
				if zp == op:
					break
				z = r
				op = 1 - zp
			elif s[r] == '0':
				op = r % 2
				if zp == op:
					break
				o = r
				zp = 1 - op
			r += 1
		b = r - l
		c = pr - l
		ans += b * (b + 1) // 2
		ans -= c * (c + 1) // 2
		l = max(z, o) + 1
		pr = r
	print(ans)


for _ in range(int(input())):
	s = input()
	ln = len(s)
	(recZero, recOne) = ([-1] * ln, [-1] * ln)
	(lastZero, lastOne) = (-1, -1)
	for i in range(0, ln):
		if s[i] == '0':
			recZero[i] = i
			lastZero = i
		elif i > 0:
			recZero[i] = lastZero
		if s[i] == '1':
			recOne[i] = i
			lastOne = i
		elif i > 0:
			recOne[i] = lastOne
	mp = [0] * ln
	mp[0] = 0
	result = 1
	for i in range(1, ln):
		if s[i] == '?':
			mp[i] = mp[i - 1]
		elif s[i] == '1':
			if recZero[i - 1] == recOne[i - 1]:
				mp[i] = 0
			elif recZero[i - 1] > recOne[i - 1]:
				if recZero[i - 1] & 1 != i & 1:
					mp[i] = mp[recZero[i - 1]]
				else:
					mp[i] = recZero[i - 1] + 1
			elif recOne[i - 1] & 1 == i & 1:
				mp[i] = mp[recOne[i - 1]]
			else:
				mp[i] = recOne[i - 1] + 1
		elif recZero[i - 1] == recOne[i - 1]:
			mp[i] = 0
		elif recZero[i - 1] > recOne[i - 1]:
			if recZero[i - 1] & 1 == i & 1:
				mp[i] = mp[recZero[i - 1]]
			else:
				mp[i] = recZero[i - 1] + 1
		elif recOne[i - 1] & 1 != i & 1:
			mp[i] = mp[recOne[i - 1]]
		else:
			mp[i] = recOne[i - 1] + 1
		result += i - mp[i] + 1
	print(result)


for _ in range(int(input())):
	a = 0
	e0 = 0
	e1 = 0
	ee = 0
	for i in input():
		if i == '?':
			(e0, e1) = (e1, e0)
			ee += 1
		elif i == '1':
			e1 = ee + e0 + 1
			e0 = 0
			ee = 0
		else:
			e0 = ee + e1 + 1
			e1 = 0
			ee = 0
		a += e0 + e1 + ee
	print(a)


def ff(n):
	return sum(range(n + 1))
for _ in range(int(input())):
	s = input()
	x = 0
	ch = ''
	chp = ''
	res = 0
	q = 0
	qq = False
	for i in s:
		if i == '?':
			if chp in ['', '?']:
				q += 1
			else:
				q = 1
		if ch != i or i == '?':
			x += 1
		if ch == i:
			res += ff(x)
			if chp != '?':
				q = 0
			res -= ff(q)
			qq = True
			x = q + 1
		if i != '?':
			ch = i
		elif ch:
			ch = '1' if ch == '0' else '0'
		chp = i
	res += ff(x)
	print(res)


t = int(input())
while t:
	t -= 1
	arr = [i for i in input()]
	for i in range(1, len(arr), 2):
		if arr[i] == '1':
			arr[i] = '0'
		elif arr[i] == '0':
			arr[i] = '1'
	start = 0
	end = -1
	zero = 0
	one = 0
	ans = 0
	while end + 1 < len(arr):
		end += 1
		if arr[end] == '1':
			one += 1
		elif arr[end] == '0':
			zero += 1
		while zero > 0 and one > 0:
			if arr[start] == '1':
				one -= 1
			elif arr[start] == '0':
				zero -= 1
			start += 1
		ans += end - start + 1
	print(ans)


for t in range(int(input())):
	s = input()
	(ans, last0, last1) = (0, 0, 0)
	for i in range(len(s)):
		if s[i] == '0':
			last0 += 1
			last1 = 0
			ans += last0
		elif s[i] == '1':
			last1 += 1
			last0 = 0
			ans += last1
		else:
			last0 += 1
			last1 += 1
			ans += max(last0, last1)
		(last0, last1) = (last1, last0)
	print(ans)


for ttt in range(int(input())):
	s = input()
	n = len(s)
	(ans, max0, max1) = (0, 0, 0)
	for i in range(n):
		if s[i] == '0':
			max0 += 1
			max1 = 0
			ans += max0
		elif s[i] == '1':
			max1 += 1
			max0 = 0
			ans += max1
		else:
			max0 += 1
			max1 += 1
			ans += max(max1, max0)
		(max0, max1) = (max1, max0)
	print(ans)


import sys
import math
import heapq
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key
input = stdin.readline
m = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)
T = int(input())
for _ in range(T):
	s = input().strip()
	n = len(s)
	dp = [[0] * (n + 1) for _ in range(2)]
	ans = 0
	for i in range(1, n + 1):
		if s[i - 1] == '0':
			dp[0][i] = dp[1][i - 1] + 1
			dp[1][i] = 0
		elif s[i - 1] == '1':
			dp[1][i] = dp[0][i - 1] + 1
			dp[0][i] = 0
		else:
			dp[0][i] = dp[1][i - 1] + 1
			dp[1][i] = dp[0][i - 1] + 1
		ans += max(dp[0][i], dp[1][i])
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	dp = [[0, 0] for i in range(n)]
	if s[0] == '0':
		dp[0][0] = 1
	elif s[0] == '1':
		dp[0][1] = 1
	else:
		dp[0][0] = 1
		dp[0][1] = 1
	for i in range(1, n):
		if s[i] == '?':
			dp[i][0] = dp[i - 1][1] + 1
			dp[i][1] = dp[i - 1][0] + 1
		elif s[i] == '1':
			dp[i][0] = 0
			dp[i][1] = dp[i - 1][0] + 1
		else:
			dp[i][0] = dp[i - 1][1] + 1
			dp[i][1] = 0
	ans = 0
	for (i, j) in dp:
		ans += max(i, j)
	print(ans)


for _ in range(int(input())):
	(o, z) = (1, 1)
	ans = 0
	s = input()
	for i in s:
		if i == '?':
			ans += max(o, z)
			(o, z) = (z + 1, o + 1)
		if i == '0':
			ans += z
			(o, z) = (z + 1, 1)
		if i == '1':
			ans += o
			(o, z) = (1, o + 1)
	print(ans)


import math

def f(x):
	return x * (x + 1) // 2
t = int(input())
for _ in range(t):
	s = '5' + str(input())
	res = 0
	dp = [0]
	w = 0
	for i in range(1, len(s)):
		if s[i] == '?':
			w += 1
			dp.append(dp[-1] + 1)
		elif s[i] == '0':
			if s[i - 1] == '1':
				dp.append(dp[-1] + 1)
			elif s[i - 1] == '0':
				dp.append(1)
			elif (int(s[i]) + w) % 2 != int(s[i - w - 1]):
				dp.append(dp[-1] + 1)
			else:
				dp.append(1 + w)
			w = 0
		else:
			if s[i - 1] == '0':
				dp.append(dp[-1] + 1)
			elif s[i - 1] == '1':
				dp.append(1)
			elif (int(s[i]) + w) % 2 != int(s[i - w - 1]):
				dp.append(dp[-1] + 1)
			else:
				dp.append(1 + w)
			w = 0
		res += dp[-1]
	print(res)


n = int(input())
for i in range(n):
	a = input()
	b = list(a)
	c = len(b)
	start = 0
	idx = 0
	if b[0] == '?':
		idx = -1
	res = 1
	for j in range(1, c):
		if b[j] != '?':
			if idx != -1:
				if b[idx] == b[j] and (j - idx - 1) % 2 == 0 or (b[idx] != b[j] and (j - idx - 1) % 2 == 1):
					start = idx + 1
			idx = j
		res += j - start + 1
	print(res)


import sys
import math
from bisect import bisect_left
import heapq
from collections import deque
from functools import reduce
from itertools import permutations

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return input()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
for _ in range(II()):
	s = list(SI())
	ans = 0
	count = 1
	last = s[0]
	temp = 0
	for i in range(1, len(s)):
		if s[i] != '?':
			if s[i] != last:
				count += 1
			else:
				ans += count * (count + 1) // 2
				ans += count * temp
				count = 1
				newLast = s[i]
				l = i - 1
				while l > 0:
					if s[l] == newLast:
						break
					else:
						newLast = str(1 - int(newLast))
					l -= 1
				temp = i - l - 1
			last = s[i]
		else:
			count += 1
			if last != '?':
				last = str(1 - int(last))
	ans += count * (count + 1) // 2
	ans += count * temp
	print(ans)


t = int(input())

def binary_search(arr, low, high, x):
	if high >= low:
		mid = (high + low) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binary_search(arr, low, mid - 1, x)
		else:
			return binary_search(arr, mid + 1, high, x)
	else:
		return -1
for _ in range(t):
	s = input()
	n = len(s)
	low = 0
	high = 0
	end = []
	length = []
	main = []
	while high < n:
		if s[high] == '?':
			while high < n and s[high] == '?':
				high += 1
			end.append(high - 1)
			length.append(high - low)
			low = high
		else:
			high += 1
			low += 1
	y = len(end)
	ans = 0
	low = 0
	high = 0
	p = -1
	q = 0
	while high < n:
		if s[high] == '?':
			high += 1
			continue
		elif s[high] == '1' and p == -1:
			p = high % 2
			high += 1
			q = 1
		elif s[high] == '0' and p == -1:
			p = high % 2
			high += 1
			q = 0
		elif s[high] == '0' and q == 1 or (s[high] == '1' and q == 0):
			if high % 2 != p:
				high += 1
				continue
			else:
				ans += (high - low) * (high - low + 1) // 2
				low = high
				q = 0
				p = -1
				if binary_search(end, 0, y - 1, high - 1) != -1:
					x = binary_search(end, 0, y - 1, high - 1)
					low -= length[x]
					ans -= length[x] * (length[x] + 1) // 2
		elif s[high] == '0' and q == 0 or (s[high] == '1' and q == 1):
			if high % 2 == p:
				high += 1
				continue
			else:
				ans += (high - low) * (high - low + 1) // 2
				low = high
				q = 0
				p = -1
				if binary_search(end, 0, y - 1, high - 1) != -1:
					x = binary_search(end, 0, y - 1, high - 1)
					low -= length[x]
					ans -= length[x] * (length[x] + 1) // 2
	ans += (high - low) * (high - low + 1) // 2
	print(ans)


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	a = [i for i in input()]
	n = len(a)
	i = 0
	j = 0
	ans = 0
	ct = 0
	while i < n:
		while j < n:
			if i == j:
				if a[j] == '?':
					ct += 1
				j += 1
			elif a[j] == '?':
				ct += 1
				j += 1
			else:
				if ct == j - i:
					j += 1
				elif a[j - ct - 1] == a[j]:
					if ct % 2:
						j += 1
					else:
						while i != j - ct:
							ans += j - i
							i += 1
				elif ct % 2:
					while i != j - ct:
						ans += j - i
						i += 1
				else:
					j += 1
				ct = 0
		break
	while i != j - 1:
		ans += j - i
		i += 1
	print(ans + 1)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
from math import inf, ceil, sqrt
from collections import defaultdict
for _ in range(int(input())):
	s = str(input())
	(n, ans) = (len(s), 0)
	dp = [[0, 0] for _ in range(n + 1)]
	for i in range(1, n + 1):
		if s[i - 1] == '0':
			dp[i][0] = 1 + dp[i - 1][1]
		elif s[i - 1] == '1':
			dp[i][1] = 1 + dp[i - 1][0]
		else:
			dp[i][0] = 1 + dp[i - 1][1]
			dp[i][1] = 1 + dp[i - 1][0]
		ans += max(dp[i][0], dp[i][1])
	print(ans)


for _ in range(int(input())):
	s = input()
	(w, e, q) = (0, 0, 0)
	for i in s:
		if i == '0':
			e += 1
			w = 0
		elif i == '1':
			w += 1
			e = 0
		else:
			w += 1
			e += 1
		q += max(e, w)
		(w, e) = (e, w)
	print(q)


n = int(input())
while n > 0:
	try:
		s = list(input())
		(value, mark, ans) = (0, 0, 0)
		for i in range(0, len(s)):
			if s[i] != '?':
				if s[i] == s[i - 1]:
					value = mark
				mark = 0
			else:
				if s[i - 1] == '1':
					s[i] = '0'
				else:
					s[i] = '1'
				mark += 1
			value += 1
			ans += value
		print(ans)
		n -= 1
	except:
		break


for _ in range(int(input())):
	s = list(input())
	ret = 0
	dp = [[0, 0] for _ in range(len(s) + 1)]
	for i in range(1, len(s) + 1):
		if s[i - 1] != '0':
			dp[i][0] = dp[i - 1][1] + 1
		if s[i - 1] != '1':
			dp[i][1] = dp[i - 1][0] + 1
		ret += max(dp[i][0], dp[i][1])
	print(ret)


import math
for _ in range(int(input())):
	s = input()
	ans = 0
	j = 0
	for i in range(len(s)):
		if i % 2 == 0 and s[i] == '1':
			continue
		if i % 2 != 0 and s[i] == '0':
			continue
		j = max(j, i + 1)
		while j < len(s) and (j % 2 == 0 and s[j] != '1' or (j % 2 != 0 and s[j] != '0')):
			j += 1
		ans += j - i
	j = 0
	for i in range(len(s)):
		if i % 2 == 0 and s[i] == '0':
			continue
		if i % 2 != 0 and s[i] == '1':
			continue
		j = max(j, i + 1)
		while j < len(s) and (j % 2 == 0 and s[j] != '0' or (j % 2 != 0 and s[j] != '1')):
			j += 1
		ans += j - i
	prev = -1
	for i in range(len(s) + 1):
		if i == len(s) or s[i] != '?':
			k = i - prev - 1
			if k > 0:
				ans -= k * (k + 1) // 2
			prev = i
	print(ans)


t = int(input())
for test in range(t):
	s = input()
	arr = []
	count = 1
	prev = 0
	i = 0
	while i < len(s):
		if i == len(s) - 1 and s[i] != '?':
			arr.append([s[prev], s[i], count])
			i += 1
		elif s[i] == '?':
			z = 0
			while s[i] == '?':
				z += 1
				i += 1
				if i == len(s):
					break
			arr.append(['?', z])
			prev = i
			count = 1
		elif s[i] == '1' and s[i + 1] == '0' or (s[i] == '0' and s[i + 1] == '1'):
			count += 1
			i += 1
		else:
			arr.append([s[prev], s[i], count])
			count = 1
			prev = i + 1
			i += 1
	ans = 0
	if arr[0][0] == '?':
		if len(arr) == 1:
			ans = arr[0][1] * (arr[0][1] + 1) // 2
			print(ans)
			continue
		else:
			arr[1][2] += arr[0][1]
			arr[0] = []
	for i in range(len(arr)):
		if arr[i] != []:
			if i + 1 == len(arr):
				break
			if arr[i + 1][0] == '?':
				if i + 2 == len(arr):
					arr[i][2] += arr[i + 1][1]
					arr[i + 1] = []
					break
				elif arr[i + 1][1] % 2 == 0:
					if arr[i][1] != arr[i + 2][0]:
						arr[i + 2][2] += arr[i + 1][1] + arr[i][2]
						arr[i] = []
						arr[i + 1] = []
					else:
						arr[i][2] += arr[i + 1][1]
						arr[i + 2][2] += arr[i + 1][1]
						ans -= arr[i + 1][1] * (arr[i + 1][1] + 1) // 2
						arr[i + 1] = []
				elif arr[i][1] == arr[i + 2][0]:
					arr[i + 2][2] += arr[i + 1][1] + arr[i][2]
					arr[i] = []
					arr[i + 1] = []
				else:
					arr[i][2] += arr[i + 1][1]
					arr[i + 2][2] += arr[i + 1][1]
					ans -= arr[i + 1][1] * (arr[i + 1][1] + 1) // 2
					arr[i + 1] = []
	for i in range(len(arr)):
		if arr[i] != []:
			ans += arr[i][2] * (arr[i][2] + 1) // 2
	print(ans)


import sys
from math import gcd, sqrt
sys.setrecursionlimit(10 ** 5)
inf = float('inf')
en = lambda x: list(enumerate(x))
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())

def solve():
	s = input()
	a = b = c = d = -1
	ans = 0
	for (j, i) in enumerate(s):
		if i != '?':
			if j % 2:
				if i == '0':
					a = j
				else:
					c = j
			elif i == '0':
				b = j
			else:
				d = j
		x = max(min(a, c), min(b, d), min(a, b), min(c, d))
		ans += j - x
	print(ans)
for _ in range(ii()):
	solve()


import bisect
from collections import Counter

def main(s):
	f = []
	n = len(s)
	for i in range(n):
		f.append([0, 0])
	s0 = 0
	s1 = 0
	ans = 0
	for i in range(n):
		c = s[i]
		if c == '0':
			f[i][1] = 0
			f[i][0] = (f[i - 1][1] if i > 0 else 0) + 1
			ans += sum(f[i])
		elif c == '1':
			f[i][1] = (f[i - 1][0] if i > 0 else 0) + 1
			f[i][0] = 0
			ans += sum(f[i])
		else:
			f[i][1] = (f[i - 1][0] if i > 0 else 0) + 1
			f[i][0] = (f[i - 1][1] if i > 0 else 0) + 1
			ans += max(f[i])
	return ans
t = int(input())
outputs = []
for _ in range(t):
	s = input()
	output = main(s)
	outputs.append(output)
for o in outputs:
	print(o)


for s in [*open(0)][1:]:
	b = c = d = e = i = 0
	for C in s:
		if C < '1':
			c = d + 1
			d = 0
			e = c
		elif C < '?':
			d = c + 1
			c = 0
			e = d
		else:
			(c, d) = (d + 1, c + 1)
			e += 1
		b += e
		i += 1
	print(b - e)


for _ in range(int(input())):
	s = input()
	l = [-1, -1]
	(ans, n) = (0, len(s))
	for i in range(n):
		if s[i] == '0' or s[i] == '1':
			l[int(s[i]) ^ i % 2] = i
		mn = min(l)
		ans += i - mn
	print(ans)


n = int(input())
while n > 0:
	n = n - 1
	s = input()
	start = 0
	idx = 0
	if s[0] == '?':
		idx = -1
	res = 1
	for i in range(1, len(s)):
		if s[i] != '?':
			if idx != -1:
				if s[idx] == s[i] and (i - idx - 1) % 2 == 0 or (s[idx] != s[i] and (i - idx - 1) % 2 == 1):
					start = idx + 1
			idx = i
		res += i - start + 1
	print(int(res))


import re
g = lambda p: sum((l * l + l >> 1 for l in map(len, re.split(p, s))))
for s in [*open(0)][1:]:
	s = ''.join((chr(ord(x) ^ i & 1) for (i, x) in enumerate(s[:-1])))
	print(g('0') + g('1') - g('0|1'))


def main():
	import sys
	read = sys.stdin.read
	readline = sys.stdin.readline
	INF = float('INF')
	MOD = 10 ** 9 + 7
	sys.setrecursionlimit(10 ** 5)
	T = int(readline())
	for _ in range(T):
		S = readline().rstrip()
		ans = 0
		l = 0
		m = 0
		last = ''
		for char in S:
			if char == '0' or char == '1':
				if last != char:
					l += 1
					ans += l
				else:
					l = m + 1
					ans += l
				m = 0
				last = char
			else:
				l += 1
				ans += l
				m += 1
				if last == '1':
					last = '0'
				elif last == '0':
					last = '1'
		print(ans)
main()


from collections import defaultdict
from collections import deque
from sys import stdout
for _ in range(int(input())):
	s = input()
	n = len(s)
	d0 = 0
	if s[0] == '?' or s[0] == '0':
		d0 = 1
	d1 = 0
	if s[0] == '?' or s[0] == '1':
		d1 = 1
	ans = 1
	for i in range(1, n):
		if s[i] == '0':
			d0 = d1 + 1
			d1 = 0
			ans += d0
		elif s[i] == '1':
			d1 = d0 + 1
			d0 = 0
			ans += d1
		else:
			(d0, d1) = (d1 + 1, d0 + 1)
			ans += max(d0, d1)
	print(ans)


import sys
import math
import collections
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
r = sys.stdin.readline
for _ in range(int(r())):
	S = r().rstrip()
	idx = 0
	ans = 0
	plus = 0
	SL = len(S)
	while 1:
		tempidx = 0
		stack = 0
		flag = 1
		now = ''
		if idx >= SL:
			break
		while 1:
			if now:
				now = str(1 - int(now))
			if idx + tempidx >= SL:
				break
			if S[idx + tempidx] == '?':
				tempidx += 1
				stack += 1
			else:
				if flag:
					now = S[idx + tempidx]
					flag = 0
				if now != S[idx + tempidx]:
					break
				tempidx += 1
				stack = 0
		idx += tempidx
		ans += plus * tempidx + tempidx * (tempidx - 1) // 2 + tempidx
		plus = stack
	print(ans)


import math, sys
from itertools import permutations
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
MOD = int(1000000000.0) + 7
INF = float('inf')

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def solve():
	s = list(input())
	n = len(s)
	q = s.count('?')
	a1 = [False for i in range(n)]
	a2 = [False for i in range(n)]
	for i in range(0, n, 2):
		if s[i] == '0' or s[i] == '?':
			a1[i] = True
	for i in range(1, n, 2):
		if s[i] == '1' or s[i] == '?':
			a1[i] = True
	for i in range(0, n, 2):
		if s[i] == '1' or s[i] == '?':
			a2[i] = True
	for i in range(1, n, 2):
		if s[i] == '0' or s[i] == '?':
			a2[i] = True
	ans = 0
	i = 0
	while i < n:
		if a1[i]:
			cnt = 0
			while i < n and a1[i]:
				i += 1
				cnt += 1
			ans += cnt * (cnt + 1) // 2
		else:
			i += 1
	i = 0
	while i < n:
		if a2[i]:
			cnt = 0
			while i < n and a2[i]:
				i += 1
				cnt += 1
			ans += cnt * (cnt + 1) // 2
		else:
			i += 1
	i = 0
	while i < n:
		if s[i] == '?':
			cnt = 0
			while i < n and s[i] == '?':
				i += 1
				cnt += 1
			ans -= cnt * (cnt + 1) // 2
		else:
			i += 1
	print(ans)
ts = 1
ts = int(input())
for t in range(1, ts + 1):
	solve()


def solve(s):
	n = len(s)
	dp = [1 if s[0] in '0?' else 0, 1 if s[0] in '1?' else 0]
	ans = max(dp)
	for i in range(1, n):
		if s[i] == '0':
			dp = [1 + dp[1], 0]
			ans += sum(dp)
		elif s[i] == '1':
			dp = [0, 1 + dp[0]]
			ans += sum(dp)
		else:
			dp = [1 + dp[1], 1 + dp[0]]
			ans += max(dp)
	return ans
for t in range(int(input())):
	s = input()
	print(solve(s))


import time

def main():
	t = i_input()
	for tt in range(t):
		s = input()
		dp0 = 0
		dp1 = 0
		out = 0
		for (i, ss) in enumerate(s):
			if ss == '?':
				dp0 += 1
				dp1 += 1
			elif ss == str(i % 2):
				dp0 += 1
				dp1 = 0
			else:
				dp1 += 1
				dp0 = 0
			out += max(dp0, dp1)
		print(out)

def i_input():
	return int(input())

def l_input():
	return input().split()

def li_input():
	return list(map(int, l_input()))

def il_input():
	return list(map(int, l_input()))
TT = time.time()
main()


def solve(s):
	last_number = 'x'
	last_number_sol = 0
	q_count = 0
	ans = []
	sol = 0
	for i in range(len(s)):
		char = s[i]
		if char == '?':
			q_count += 1
			sol += q_count
			if last_number != 'x':
				sol += last_number_sol
		else:
			sol += q_count + 1
			if last_number == char and q_count % 2 == 1:
				sol += last_number_sol
			elif (last_number != char and last_number != 'x') and q_count % 2 == 0:
				sol += last_number_sol
			q_count = 0
			last_number = char
			last_number_sol = sol
		ans.append(sol)
		sol = 0
	return sum(ans)
test_cases = int(input())
for test_case in range(test_cases):
	string = input()
	print(solve(string))


from sys import stdin
from math import gcd
input = lambda : stdin.readline().strip()
for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = -1
	i = 0
	nd = 0
	sum1 = 0
	while i < n:
		if s[i] == '?':
			if ans != -1:
				ans = ans ^ 1
				nd += 1
				i += 1
			else:
				nd += 1
				i += 1
		elif ans == -1:
			ans = int(s[i]) ^ 1
			i += 1
			nd += 1
		elif ans != int(s[i]):
			sum1 += nd * (nd + 1) // 2
			nd = 0
			nk = 0
			while i > 0:
				if s[i - 1] == '?':
					i -= 1
					nk += 1
				else:
					break
			sum1 -= nk * (nk + 1) // 2
			ans = -1
		else:
			ans = ans ^ 1
			nd += 1
			i += 1
	if nd != 0:
		sum1 += nd * (nd + 1) // 2
	print(sum1)


def answer():
	(size, ans) = (1, 0)
	(prev, q, prevq) = (s[0], 0, 0)
	for i in range(1, n):
		if s[i] == prev and prev != '?':
			ans -= q * (q + 1) // 2
			ans += size * (size + 1) // 2
			size = q + 1
		else:
			size += 1
		if s[i] == '?':
			if prev == '1':
				prev = '0'
			elif prev == '0':
				prev = '1'
			q += 1
		else:
			q = 0
			prev = s[i]
	ans += size * (size + 1) // 2
	return ans
for T in range(int(input())):
	s = input()
	n = len(s)
	print(answer())


def solve(S):
	ans = 0
	N = len(S)
	left = 0
	last_c_idx = 0
	for i in range(N):
		c = S[i]
		if S[i] != '?' and S[last_c_idx] != '?':
			if i - last_c_idx & 1:
				target = str(1 - int(S[i]))
			else:
				target = S[i]
			if S[last_c_idx] != target:
				last_c_idx += 1
				left = last_c_idx
		ans += i - left + 1
		if c != '?':
			last_c_idx = i
	return ans
T = int(input())
for _ in range(T):
	S = input()
	print(solve(S))


from collections import defaultdict as df
from collections import deque as dq
import sys
from math import factorial as fa
import bisect
import random
from heapq import heappush, heappop
from math import gcd
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
mod = pow(10, 9) + 7
for _ in range(t):
	s = input().rstrip()
	n = len(s)
	has_letter = False
	last_letter = 0
	start = 0
	end = 0
	ans = 0
	cons_q = 0
	while True:
		if end >= n:
			break
		if s[end] == '?':
			end += 1
			if not last_letter:
				continue
			elif last_letter == '1':
				last_letter = '0'
			else:
				last_letter = '1'
		elif not has_letter:
			has_letter = True
			last_letter = s[end]
			end += 1
		elif last_letter != s[end]:
			last_letter = s[end]
			end += 1
		else:
			mul = end - start
			ans += mul * (mul + 1) // 2 - mul - ((cons_q + 1) * cons_q // 2 - cons_q)
			temp = s[end]
			temp_i = start
			start = end - 1
			cons_q = 0
			ll = s[end]
			while True:
				if s[start] == ll:
					start += 1
					break
				if s[start] == '?':
					ll = '1' if ll == '0' else '0'
				else:
					ll = s[start]
				start -= 1
				cons_q += 1
			last_letter = s[end]
			end += 1
	mul = end - start
	ans += mul * (mul + 1) // 2 - mul - ((cons_q + 1) * cons_q // 2 - cons_q)
	print(ans + n)


from math import *

def seg_cnt(f, n):
	cnt = 0
	start = None
	for i in range(n + 1):
		eq = f(i) if i != n else False
		if eq and start == None:
			start = i
		elif not eq and start != None:
			length = i - start
			cnt += length * (length + 1) // 2
			start = None
	return cnt
for _ in range(int(input())):
	str = input()
	n = len(str)
	a = seg_cnt(lambda i: str[i] == '?' or str[i] == '01'[i % 2], n)
	b = seg_cnt(lambda i: str[i] == '?' or str[i] == '10'[i % 2], n)
	c = seg_cnt(lambda i: str[i] == '?', n)
	print(a + b - c)


def lcm(x, y):
	return x * y // math.gcd(x, y)

def prob():
	s = input()
	ans = 0
	x = [-1, -1]
	for i in range(len(s)):
		y = ord(s[i]) - ord('0')
		if y == 0 or y == 1:
			x[y ^ i % 2] = i
		ans += i - min(x)
	print(ans)
t = 1
t = int(input())
for _ in range(0, t):
	prob()


for _ in range(int(input())):
	s = input()
	ans = [0] * len(s)
	ans[0] = 1
	if s[0] == '0':
		x = 1
		y = 0
	elif s[0] == '1':
		x = 0
		y = 1
	else:
		x = 1
		y = 1
	for i in range(1, len(s)):
		if s[i] == '1':
			if s[i - 1] == '0':
				ans[i] = ans[i - 1] + 1
				y = x + 1
				x = 0
			elif s[i - 1] == '1':
				ans[i] = 1
				x = 0
				y = 1
			else:
				y = x + 1
				x = 0
				ans[i] = y
		elif s[i] == '0':
			if s[i - 1] == '1':
				ans[i] = ans[i - 1] + 1
				x = y + 1
				y = 0
			elif s[i - 1] == '0':
				ans[i] = 1
				y = 0
				x = 1
			else:
				x = y + 1
				y = 0
				ans[i] = x
		elif s[i] == '?':
			ans[i] = ans[i - 1] + 1
			temp = x
			x = y + 1
			y = temp + 1
	sm = 0
	for i in ans:
		sm += i
	print(sm)


for _ in range(int(input())):
	ar = input()
	(zero, one, ans) = (0, 0, 0)
	for i in ar:
		if i == '0':
			zero += 1
			one = 0
			ans += zero
		elif i == '1':
			one += 1
			zero = 0
			ans += one
		else:
			zero += 1
			one += 1
			ans += max(zero, one)
		(zero, one) = (one, zero)
	print(ans)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	s = input().rstrip()
	n = len(s)
	ans = 0
	q = 0
	last = '?'
	cur_len = 0
	for c in s:
		if c == '?':
			q += 1
			cur_len += 1
			if last == '1':
				last = '0'
			elif last == '0':
				last = '1'
		elif c == '1':
			if last == '1':
				ans += cur_len * (cur_len + 1) // 2
				cur_len = q + 1
				ans -= q * (q + 1) // 2
			else:
				cur_len += 1
			last = c
			q = 0
		else:
			if last == '0':
				ans += cur_len * (cur_len + 1) // 2
				cur_len = q + 1
				ans -= q * (q + 1) // 2
			else:
				cur_len += 1
			last = c
			q = 0
	ans += cur_len * (cur_len + 1) // 2
	print(ans)


import sys, os
from io import BytesIO, IOBase
from functools import lru_cache
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
tc = 1
tc = int(input())
for test in range(1, tc + 1):
	a = list(input())
	n = len(a)
	x = [-1, -1]
	ans = 0
	for i in range(n):
		if a[i] == '0':
			x[0 ^ i % 2] = i
		if a[i] == '1':
			x[1 ^ i % 2] = i
		ind = min(x)
		ans += i - ind
	print(ans)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	string = sys.stdin.readline().rstrip()
	beautiful = 0
	i = 0
	dp = [0 for _ in range(len(string))]
	dp[-1] = 1
	i = len(string) - 2
	while i >= 0:
		q = 0
		k = string[i + 1]
		while string[i] == '?' and i >= 0:
			dp[i] = dp[i + 1] + 1
			i -= 1
			q += 1
		if dp[0]:
			break
		if k == '?':
			dp[i] = dp[i + 1] + 1
		elif string[i] != k:
			if q % 2:
				dp[i] = 1 + q
			else:
				dp[i] = dp[i + 1] + 1
		elif q:
			if q % 2 == 0:
				dp[i] = 1 + q
			else:
				dp[i] = dp[i + 1] + 1
		else:
			dp[i] = 1
		i -= 1
		q = 0
	print(sum(dp))


T = int(input())
for t in range(T):
	a = list(input())
	c = 1
	count = 0
	q = 0
	for i in range(1, len(a)):
		if a[i] == '0':
			if a[i - 1] == '0':
				count = count + c * (c + 1) // 2
				if q != 0:
					count = count - q * (q + 1) // 2
				c = q
			q = 0
		if a[i] == '1':
			if a[i - 1] == '1':
				count = count + c * (c + 1) // 2
				if q != 0:
					count = count - q * (q + 1) // 2
				c = q
			q = 0
		if a[i] == '?':
			q = q + 1
			if a[i - 1] == '1':
				a[i] = '0'
			if a[i - 1] == '0':
				a[i] = '1'
		c = c + 1
	count = count + c * (c + 1) // 2
	print(count)


import sys
input = sys.stdin.readline
from collections import Counter
for _ in range(int(input())):
	s = input()[:-1]
	ans = 0
	j = 0
	(s0, s1) = (Counter(), Counter())
	for (i, c) in enumerate(s):
		if not i % 2:
			s0[c] += 1
		else:
			s1[c] += 1
		while s0['0'] and s1['0'] or (s0['1'] and s1['1']) or (s0['0'] and s0['1']) or (s1['0'] and s1['1']):
			if not j % 2:
				s0[s[j]] -= 1
			else:
				s1[s[j]] -= 1
			j += 1
		ans += i - j + 1
	print(ans)


t = int(input())
while t:
	s = input()
	l = len(s)
	b = 0
	q = 0
	if s[0] == '?':
		q = -1
	p = 1
	i = 1
	for i in range(l):
		if s[i] != '?':
			if q != -1:
				if s[q] == s[i] and (i - q - 1) % 2 == 0 or (s[q] != s[i] and (i - q - 1) % 2 == 1):
					b = q + 1
			q = i
		p += i - b + 1
	print(p - 1)
	t -= 1


import sys
import math
input = sys.stdin.readline
imp = 'IMPOSSIBLE'
t = int(input())
for test in range(t):
	s = input()[:-1]
	p = ''
	d = ''
	ot = 0
	le = 0
	res = 0
	for i in range(len(s)):
		if not p:
			if s[i] != '?':
				ot = 0
				if le % 2 == 0:
					p = s[i]
				elif s[i] == '0':
					p = '1'
				else:
					p = '0'
			else:
				ot += 1
			le += 1
		elif s[i] == '?':
			ot += 1
			le += 1
		elif le % 2 == 0 and p == s[i] or (le % 2 == 1 and p != s[i]):
			le += 1
			ot = 0
		else:
			res = res + le * (le + 1) // 2
			if ot:
				res = res - ot * (ot + 1) // 2
			le = 1 + ot
			if ot % 2 == 0:
				p = s[i]
			elif s[i] == '0':
				p = '1'
			else:
				p = '0'
			ot = 0
	res = res + le * (le + 1) // 2
	print(res)


def main():
	t = int(input())
	for _ in range(t):
		s = input()
		n = len(s)
		dp = [[0] * 5 for _ in range(n)]
		if s[0] == '0':
			dp[0][0] = 1
		elif s[0] == '1':
			dp[0][1] = 1
		else:
			dp[0][2] = 0
			dp[0][3] = 0
			dp[0][4] = 1
		ans = sum(dp[0])
		for i in range(1, n):
			if s[i] == '0':
				dp[i][0] += dp[i - 1][1] + dp[i - 1][3] + dp[i - 1][4] + 1
			elif s[i] == '1':
				dp[i][1] += dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][4] + 1
			else:
				dp[i][2] += dp[i - 1][1] + dp[i - 1][3]
				dp[i][3] += dp[i - 1][0] + dp[i - 1][2]
				dp[i][4] += dp[i - 1][4] + 1
			ans += sum(dp[i])
		print(ans)
main()


import os
import sys
from io import BytesIO, IOBase
import math
from collections import Counter

def func(array):
	num = 0
	last_question = None
	last_number = None
	start = None
	first = None
	first_index = None
	for (i, val) in enumerate(array):
		if first is None:
			if val != '?':
				first = val
				first_index = i
				last_question = None
				last_number = i
				if start is None:
					start = i
			elif last_question is None:
				last_question = i
				start = i
			num += i - start + 1
		elif val == '?':
			num += i - start + 1
			if last_question is None or last_question < last_number:
				last_question = i
		elif val == first and (i - first_index) % 2 == 0 or (val != first and (i - first_index) % 2 != 0):
			num += i - start + 1
			last_number = i
			last_question = None
		else:
			if last_question is not None and last_question > first_index:
				start = last_question
			else:
				start = i
				last_question = None
			first_index = i
			first = val
			last_number = i
			num += i - start + 1
	return num

def main():
	num_test = int(parse_input())
	result = []
	for _ in range(num_test):
		array = parse_input()
		result.append(func(array))
	print('\n'.join(map(str, result)))
parse_input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for i in range(t):
	s = input()
	dp = [[0, 0] for i in range(len(s) + 1)]
	count = 0
	for end in range(1, len(s) + 1):
		if s[end - 1] == '?':
			dp[end][0] = dp[end - 1][1] + 1
			dp[end][1] = dp[end - 1][0] + 1
		elif s[end - 1] == '0':
			dp[end][0] = 0
			dp[end][1] = dp[end - 1][0] + 1
		else:
			dp[end][0] = dp[end - 1][1] + 1
			dp[end][1] = 0
		count += max(dp[end][0], dp[end][1])
	print(count)


from math import factorial

def print_sol(c, sol):
	print('Case #{}: {}'.format(c, sol))

def rd_int():
	return int(input())

def rd_str():
	return input()

def rd_str_lst():
	return input().split(' ')

def sp_str_lst():
	return list(input())

def rd_int_lst():
	return [int(i) for i in rd_str_lst()]

def sp_int_lst():
	return [int(i) for i in sp_str_lst()]

def main():
	t = rd_int()
	for c in range(1, t + 1):
		s = rd_str()
		last = [[-1, -1], [-1, -1]]
		ans = 0
		for i in range(len(s)):
			j = i - 1
			p = i & 1
			if s[i] != '1':
				j = min(j, max(last[0][p ^ 1], last[1][p]))
			if s[i] != '0':
				j = min(j, max(last[1][p ^ 1], last[0][p]))
			ans += i - j
			if s[i] != '?':
				last[int(s[i])][p] = i
		print(ans)
main()


n = eval(input())
for t in range(n):
	s = input()
	(w, e, q) = (0, 0, 0)
	for i in s:
		if i == '0':
			e += 1
			w = 0
		elif i == '1':
			w += 1
			e = 0
		else:
			w += 1
			e += 1
		q += max(e, w)
		(w, e) = (e, w)
	print(q)


for _ in range(int(input())):
	s = input()
	dp = [0] * len(s)
	dp[0] = 1
	qc = 0
	if s[0] == '?':
		qc = 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			if s[i] == '?':
				qc += 1
				dp[i] = dp[i - 1] + 1
			elif s[i - 1] == '?':
				if qc % 2 == 0:
					if s[i - qc - 1] != s[i]:
						dp[i] = dp[i - qc - 1] + qc + 1
					else:
						dp[i] = qc + 1
				elif s[i - qc - 1] == s[i]:
					dp[i] = dp[i - qc - 1] + qc + 1
				else:
					dp[i] = qc + 1
				qc = 0
			else:
				dp[i] = dp[i - 1] + 1
				qc = 0
		elif s[i] == s[i - 1]:
			if s[i] == '?':
				dp[i] = dp[i - 1] + 1
				qc += 1
			else:
				dp[i] = 1
				qc = 0
	print(sum(dp))


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	mx0 = 0
	mx1 = 0
	ans = 0
	for i in range(n):
		if s[i] == '0':
			mx0 += 1
			mx1 = 0
			ans += mx0
		elif s[i] == '1':
			mx1 += 1
			mx0 = 0
			ans += mx1
		else:
			mx0 += 1
			mx1 += 1
			ans += max(mx0, mx1)
		temp = mx0
		mx0 = mx1
		mx1 = temp
	print(ans)


t = int(input())
while t != 0:
	s = input()
	(one, zero) = (0, 0)
	ans = 0
	for i in s:
		if i == '1':
			one += 1
			zero = 0
			ans += one
		elif i == '0':
			zero += 1
			one = 0
			ans += zero
		else:
			one += 1
			zero += 1
			ans += max(one, zero)
		(zero, one) = (one, zero)
	print(ans)
	t -= 1


def solve(S):
	N = len(S)
	qlen = [0] * (N + 1)
	for i in range(N - 1, -1, -1):
		if S[i] == '?':
			qlen[i] = qlen[i + 1] + 1
	blen = [0] * N
	blen[N - 1] = 1
	for i in range(N - 2, -1, -1):
		if S[i] == '?':
			blen[i] = 1 + blen[i + 1]
		elif S[i + 1] == '?':
			if i + qlen[i + 1] == N - 1:
				blen[i] = 1 + blen[i + 1]
			elif qlen[i + 1] & 1 == 0:
				if S[i + 1 + qlen[i + 1]] != S[i]:
					blen[i] = 1 + blen[i + 1]
				else:
					blen[i] = 1 + qlen[i + 1]
			elif S[i + 1 + qlen[i + 1]] == S[i]:
				blen[i] = 1 + blen[i + 1]
			else:
				blen[i] = 1 + qlen[i + 1]
		elif S[i + 1] != S[i]:
			blen[i] = 1 + blen[i + 1]
		else:
			blen[i] = 1
	print(sum(blen))
T = int(input())
for t in range(T):
	S = input()
	solve(S)


xx = ['0', '1']
yy = ['1', '0']
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	dp = [i + 1 for i in range(n)]
	for i in range(n - 2, -1, -1):
		if s[i] == '?':
			dp[i] = dp[i + 1]
		elif s[i] == '0':
			if s[i + 1] == '1':
				dp[i] = dp[i + 1]
			elif s[i + 1] == '0':
				dp[i] = i + 1
			else:
				j = i + 1
				while j < n and (s[j] == '?' or s[j] == xx[(j - i) % 2]):
					j += 1
				dp[i] = j
		elif s[i] == '1':
			if s[i + 1] == '0':
				dp[i] = dp[i + 1]
			elif s[i + 1] == '1':
				dp[i] = i + 1
			else:
				j = i + 1
				while j < n and (s[j] == '?' or s[j] == yy[(j - i) % 2]):
					j += 1
				dp[i] = j
	ans = 0
	for i in range(n):
		ans += dp[i] - i
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	a = list(s)
	n = len(s)
	for i in range(1, n, 2):
		if a[i] == '0':
			a[i] = '1'
		elif a[i] == '1':
			a[i] = '0'
	l = 0
	ans = 0
	(zeros, ones) = (0, 0)
	for r in range(n):
		if a[r] == '0':
			zeros += 1
		elif a[r] == '1':
			ones += 1
		while zeros and ones:
			if a[l] == '0':
				zeros -= 1
			elif a[l] == '1':
				ones -= 1
			l += 1
		ans += r - l + 1
	print(ans)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from itertools import permutations
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
for ik in range(int(input())):
	s = list(input())
	n = len(s)
	par = [0] * n
	for i in range(n):
		if s[i] == '?':
			par[i] = -1
			continue
		if int(s[i]) % 2 - i % 2 == 0:
			par[i] = 0
		else:
			par[i] = 1
	ans = 0
	j = 0
	s1 = SegmentTree(par)
	for i in range(n):
		le = 0
		j = max(j, i)
		if j == i:
			last = par[i]
		if j < n and s[j] == '?':
			while j < n and s[j] == '?':
				j += 1
			if j < n:
				last = par[j]
		if j < n and s1.query(i, j - 1) == -(j - i):
			last = par[j]
		while j < n and (s[j] == '?' or last == par[j]):
			j += 1
		le = j - i
		ans += le
	print(ans)


from math import comb
t = int(input())
for tc in range(t):
	s = input()
	dp = (-1, -1)
	result = 0
	for ch in s:
		one = -1
		zero = -1
		if ch != '1':
			if dp[1] == -1:
				zero = 1
			else:
				zero = dp[1] + 1
			if ch != '?' and dp[0] != -1:
				result += comb(dp[0], 2)
		if ch != '0':
			if dp[0] == -1:
				one = 1
			else:
				one = dp[0] + 1
			if ch != '?' and dp[1] != -1:
				result += comb(dp[1], 2)
		dp = (zero, one)
	if dp[0] != -1:
		result += comb(dp[0], 2)
	if dp[1] != -1:
		result += comb(dp[1], 2)
	tmp = 0
	for i in range(len(s)):
		if s[i] == '?':
			tmp += 1
		else:
			result -= comb(tmp, 2)
			tmp = 0
	result -= comb(tmp, 2)
	print(result + len(s))


from math import sqrt, gcd, ceil, floor, log, factorial
from itertools import permutations, combinations
from collections import Counter, defaultdict
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	dp = [1] + [0] * (n - 1)
	if s[0] == '1':
		el = '1'
		ind = 0
	elif s[0] == '0':
		el = '0'
		ind = 0
	else:
		el = -1
		ind = -1
	for i in range(1, n):
		if s[i] == '1':
			if s[i - 1] == '0':
				dp[i] = 1 + dp[i - 1]
			elif s[i - 1] == '1':
				dp[i] = 1
			elif s[i - 1] == '?':
				if el == -1:
					dp[i] = 1 + dp[i - 1]
				elif (i - ind - 1) % 2 == 0 and el == '0' or ((i - ind - 1) % 2 == 1 and el == '1'):
					dp[i] = 1 + dp[i - 1]
				elif (i - ind - 1) % 2 == 0 and el == '1' or ((i - ind - 1) % 2 == 1 and el == '0'):
					dp[i] = 1 + dp[i - 1] - dp[ind]
			el = '1'
			ind = i
		elif s[i] == '0':
			if s[i - 1] == '1':
				dp[i] = 1 + dp[i - 1]
			elif s[i - 1] == '0':
				dp[i] = 1
			elif s[i - 1] == '?':
				if el == -1:
					dp[i] = 1 + dp[i - 1]
				elif (i - ind - 1) % 2 == 0 and el == '1' or ((i - ind - 1) % 2 == 1 and el == '0'):
					dp[i] = 1 + dp[i - 1]
				elif (i - ind - 1) % 2 == 0 and el == '0' or ((i - ind - 1) % 2 == 1 and el == '1'):
					dp[i] = 1 + dp[i - 1] - dp[ind]
			el = '0'
			ind = i
		else:
			dp[i] = 1 + dp[i - 1]
	print(sum(dp))


for s in [*open(0)][1:]:
	n = len((s := s[:-1]))
	S = i = 0
	P = [-1] * 2
	l = [-1] * 2
	for c in s:
		if c < '?':
			p = int(c) ^ i & 1
			l[p] = i
			P[p] = l[p ^ 1]
		S += i - max(P)
		i += 1
	print(S)


t = int(input())
for hh in range(0, t):
	s = input()
	n = len(s)
	prvset_idx = -1
	leng = 0
	cnt = 0
	for i in range(0, n):
		if prvset_idx == -1 or s[i] == '?':
			leng += 1
			cnt += leng
		else:
			diff = i - prvset_idx
			if diff % 2 == 1:
				if s[i] == s[prvset_idx]:
					new_idx = prvset_idx + 1
					dist = i - new_idx
					leng = dist + 1
					cnt += leng
				else:
					leng += 1
					cnt += leng
			elif s[i] != s[prvset_idx]:
				new_idx = prvset_idx + 1
				dist = i - new_idx
				leng = dist + 1
				cnt += leng
			else:
				leng += 1
				cnt += leng
		if s[i] != '?':
			prvset_idx = i
	print(cnt)


cases = int(input())
for _ in range(cases):
	st = input()
	n = len(st)
	dp = [0] * n
	last0 = [-1] * n
	last1 = [-1] * n
	for i in range(n):
		if st[i] == '0':
			last0[i] = i
		elif i >= 1:
			last0[i] = last0[i - 1]
	for i in range(n):
		if st[i] == '1':
			last1[i] = i
		elif i >= 1:
			last1[i] = last1[i - 1]
	dp[0] = 0
	ans = 1
	for i in range(1, n):
		if st[i] == '?':
			dp[i] = dp[i - 1]
		elif st[i] == '1':
			if last0[i - 1] == last1[i - 1]:
				dp[i] = 0
			elif last0[i - 1] > last1[i - 1]:
				ida = last0[i - 1]
				if ida & 1 != i & 1:
					dp[i] = dp[ida]
				else:
					dp[i] = ida + 1
			else:
				ida = last1[i - 1]
				if ida & 1 == i & 1:
					dp[i] = dp[ida]
				else:
					dp[i] = ida + 1
		elif last0[i - 1] == last1[i - 1]:
			dp[i] = 0
		elif last0[i - 1] > last1[i - 1]:
			ida = last0[i - 1]
			if ida & 1 == i & 1:
				dp[i] = dp[ida]
			else:
				dp[i] = ida + 1
		else:
			ida = last1[i - 1]
			if ida & 1 != i & 1:
				dp[i] = dp[ida]
			else:
				dp[i] = ida + 1
		ans += i - dp[i] + 1
	print(ans)


import sys
from math import *
import builtins
input = sys.stdin.readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)

def get_int():
	return int(input())

def get_list_ints():
	return list(map(int, input().split()))

def get_char_list():
	s = input()
	return list(s[:len(s) - 1])

def get_tuple_ints():
	return tuple(map(int, input().split()))

def print_iterable(p):
	print(' '.join(map(str, p)))

def main():
	p = get_int()
	for q in range(p):
		ls = get_char_list()
		final = []
		result = []
		total = 0
		count = 0
		for i in range(len(ls)):
			result += [ls[i]]
			if ls[i] == '0' or ls[i] == '1':
				if i == count:
					count = 0
				else:
					if count % 2 == 0:
						if not (ls[i] == '1' and ls[i - count - 1] == '0') and (not (ls[i] == '0' and ls[i - count - 1] == '1')):
							result.pop()
							final += [result]
							if result[-1] == '?':
								result = []
								for a in range(count):
									result += ['?']
								result += [ls[i]]
								total -= int(count * (count + 1) / 2)
							else:
								result = [ls[i]]
					elif not (ls[i] == '0' and ls[i - count - 1] == '0') and (not (ls[i] == '1' and ls[i - count - 1] == '1')):
						result.pop()
						final += [result]
						if result[-1] == '?':
							result = []
							for a in range(count):
								result += ['?']
							result += [ls[i]]
							total -= int(count * (count + 1) / 2)
						else:
							result = [ls[i]]
					count = 0
			else:
				count += 1
		final += [result]
		for j in range(len(final)):
			a = len(final[j])
			total += int(a * (a + 1) / 2)
		print(total)
	pass
main()


import sys
import math
import collections
import heapq
input = sys.stdin.readline
t = int(input())
for w in range(t):
	s = input()
	n = len(s) - 1
	prevl = 0
	c = 0
	prev = '2'
	prevq = 2
	qcount = 0
	for i in range(n):
		if s[i] == '1':
			if prev == '0':
				prevl += 1
				c += prevl
			elif prev == '1':
				c += 1
				prevl = 1
			elif prev == '2':
				prevl += 1
				c += prevl
			elif prevq == 0:
				prevl += 1
				c += prevl
				qcount = 0
			elif prevq == 2:
				prevl += 1
				c += prevl
				qcount = 0
			else:
				c += qcount + 1
				prevl = qcount + 1
				qcount = 0
		elif s[i] == '0':
			if prev == '0':
				c += 1
				prevl = 1
			elif prev == '1':
				prevl += 1
				c += prevl
			elif prev == '2':
				prevl += 1
				c += prevl
			elif prevq == 0:
				c += qcount + 1
				prevl = qcount + 1
				qcount = 0
			elif prevq == 2:
				prevl += 1
				c += prevl
				qcount = 0
			else:
				prevl += 1
				c += prevl
				qcount = 0
		elif prev == '0':
			prevl += 1
			c += prevl
			qcount += 1
			prevq = 1
		elif prev == '1':
			prevl += 1
			c += prevl
			qcount += 1
			prevq = 0
		elif prev == '2':
			prevl += 1
			c += prevl
			qcount += 1
		else:
			prevl += 1
			c += prevl
			qcount += 1
			if prevq == 1:
				prevq = 0
			elif prevq == 0:
				prevq = 1
		prev = s[i]
	print(c)


def solve(s: str) -> int:
	ans = 0
	x = [-1, -1]
	for i in range(len(s)):
		y = ord(s[i]) - ord('0')
		if y == 0 or y == 1:
			x[y ^ i % 2] = i
		ans += i - min(x)
	return ans
test_cases = int(input())
for _ in range(test_cases):
	s = input()
	print(solve(s))


for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = 0
	i = 0
	count = 0
	while i < n and s[i] == '?':
		i += 1
		count += 1
	while i < n:
		if i + 1 < n and s[i + 1] == '?':
			j = i + 1
			qs = 0
			while j < n and s[j] == '?':
				qs += 1
				j += 1
			if j < n:
				if qs & 1 and s[i] == s[j] or (qs & 1 == 0 and s[i] != s[j]):
					count += qs + 1
				else:
					count += 1
					ans += count * (count + 1) // 2 + qs * count
					count = qs
			else:
				count += qs + 1
			i = j
		elif i + 1 < n and s[i + 1] != s[i]:
			count += 1
			i += 1
		else:
			count += 1
			ans += count * (count + 1) // 2
			count = 0
			i += 1
	ans += count * (count + 1) // 2
	print(ans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
import bisect, string, math, time, functools, random, fractions
from bisect import *
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range
R = range

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def AI():
	return map(int, open(0).read().split())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def NLI(n):
	return [[int(i) for i in input().split()] for i in range(n)]

def NLI_(n):
	return [[int(i) - 1 for i in input().split()] for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RLI(n=8, a=1, b=10):
	return [random.randint(a, b) for i in range(n)]

def RI(a=1, b=10):
	return random.randint(a, b)

def INP():
	N = 10
	n = random.randint(1, N)
	a = RLI(n, 0, n - 1)
	return (n, a)

def Rtest(T):
	(case, err) = (0, 0)
	for i in range(T):
		inp = INP()
		a1 = naive(*inp)
		a2 = solve(*inp)
		if a1 != a2:
			print(inp)
			print('naive', a1)
			print('solve', a2)
			err += 1
		case += 1
	print('Tested', case, 'case with', err, 'errors')

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
alp = [chr(ord('a') + i) for i in range(26)]

def gcj(c, x):
	print('Case #{0}:'.format(c + 1), x)
show_flg = False
show_flg = True
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y
for i in range(int(input())):
	s = list(input())
	n = len(s)
	s += (' ',)
	s0 = [0]
	for i in range(n):
		s0 += (1 - s0[-1],)
	s1 = [1]
	for i in range(n):
		s1 += (1 - s1[-1],)
	x = []
	l = 0
	for i in range(n + 1):
		c = s[i]
		if c == '?' or c == str(s0[i]):
			l += 1
		else:
			if l == 0:
				continue
			x += (l,)
			l = 0
	y = []
	z = []
	l = 0
	r = 0
	for i in range(n + 1):
		c = s[i]
		if c == '?' or c == str(s1[i]):
			l += 1
		else:
			if l == 0:
				continue
			y += (l,)
			l = 0
		if c == '?':
			r += 1
		else:
			if r == 0:
				continue
			z += (r,)
			r = 0
	ans = 0
	ans += sum((i * (i + 1) // 2 for i in x))
	ans += sum((i * (i + 1) // 2 for i in y))
	ans -= sum((i * (i + 1) // 2 for i in z))
	print(ans)


n = int(input())
for _ in range(n):
	ans = 0
	a = input()
	t = a[0]
	x = -1
	d = 0
	y = -1
	for i in range(0, len(a)):
		if (a[i] == t and d % 2 == 0 or (a[i] != t and d % 2 == 1)) and t != '?' and (a[i] != '?'):
			dl = abs(i - 1 - x)
			if d != 0:
				x = y
				ans -= (d - 1) * d // 2
			else:
				x = i - 1
			if dl != 1:
				ans += (dl - 1) * dl // 2
			d = 0
		if a[i] == '?':
			d += 1
			if a[i - 1] != '?':
				y = i - 1
		if a[i] != '?':
			t = a[i]
			d = 0
	dl = abs(i - x)
	x = y
	ans += (dl - 1) * dl // 2
	ans += len(a)
	print(ans)


import io
import os
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop, heapify
from math import gcd, inf

def solve(S):
	ans = 0
	q = 0
	prev = []
	for (i, x) in enumerate(S):
		if x == '?':
			if len(prev) == q:
				prev.append(-1)
			else:
				prev.append(prev[-1] ^ 1)
			q += 1
		else:
			x = int(x)
			if len(prev) == q or prev[-1] ^ x == 1:
				prev.append(x)
				q = 0
			else:
				prev = [-1] * q + [x]
				q = 0
		ans += len(prev)
	return ans
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	S = input().decode().rstrip()
	ans = solve(S)
	print(ans)


def func():
	max1 = 0
	max0 = 0
	length = len(s)
	ans = 0
	for i in range(length):
		if s[i] == '0':
			max0 += 1
			max1 = 0
			ans += max0
		elif s[i] == '1':
			max1 += 1
			max0 = 0
			ans += max1
		else:
			max1 += 1
			max0 += 1
			ans += max(max0, max1)
		(max0, max1) = (max1, max0)
	print(ans)
for _ in range(int(input())):
	s = list(input())
	func()


def inv(x):
	if x == '0':
		return '1'
	return '0'

def unstableString(string):
	array = list(string)
	n = len(array)
	met = [0]
	ans = [1]
	for x in range(1, n):
		if array[x - 1] == '?':
			met.append(met[-1] + 1)
		else:
			met.append(0)
	expectation = array[0]
	if expectation in ('0', '1'):
		expectation = inv(expectation)
	for x in range(1, n):
		if array[x] == '?':
			ans.append(ans[-1] + 1)
		elif array[x - 1] != '?':
			if array[x - 1] != array[x]:
				ans.append(ans[-1] + 1)
			else:
				ans.append(1)
				expectation = array[x]
		elif array[x - 1] == '?':
			if array[x] == expectation:
				ans.append(ans[-1] + 1)
			else:
				ans.append(met[x] + 1)
				expectation = array[x]
		expectation = inv(expectation)
	return sum(ans)
t = int(input())
for _ in range(t):
	print(unstableString(input()))


import sys, os
import math
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		s = list(input())
		n = len(s)
		(q1, q2) = (0, 0)
		if s[0] == '?':
			q1 += 1
			k = 0
			while k < n and s[k] == '?':
				k += 1
			if k == n:
				print(n * (n + 1) // 2)
				continue
			if k & 1:
				s[0] = str(int(s[k]) ^ 1)
			else:
				s[0] = s[k]
		(out, prev) = (0, 0)
		for i in range(1, n):
			if s[i] == s[i - 1]:
				out += (i - prev) * (i - prev + 1) // 2
				if q2:
					out += q2 * (i - prev)
					q2 = 0
				if q1:
					q2 += q1
				prev = i
			if s[i] == '?':
				s[i] = str(int(s[i - 1]) ^ 1)
				q1 += 1
			else:
				q1 = 0
		out += (n - prev) * (n - prev + 1) // 2
		if q2:
			out += q2 * (n - prev)
		print(out)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def MI():
	return map(int, input().split())

def outP(var):
	sys.stdout.write(str(var) + '\n')
MOD = 10 ** 9 + 7
mod = 998244353
main()


def count_unstable(str):
	f = 0
	c1 = 0
	c2 = 0
	res = 0
	for i in range(len(str)):
		if str[i] == '?' or int(str[i]) - 0 == f:
			c1 += 1
		else:
			c1 = 0
		if str[i] == '?' or int(str[i]) - 0 == 1 - f:
			c2 += 1
		else:
			c2 = 0
		res += max(c1, c2)
		f = 1 - f
	return res
t = int(input())
for i in range(t):
	str = input()
	print(count_unstable(str))


for _ in range(int(input())):
	s = input()
	ans = [0 for i in range(len(s))]
	last_ind = -1 if s[0] == '?' else 0
	ans[0] = 1
	for i in range(1, len(s)):
		if s[i] == '?':
			ans[i] = 1 + ans[i - 1]
		elif s[i] == '0':
			if last_ind == -1:
				ans[i] += i + 1
			else:
				temp = i - last_ind - 1
				if temp % 2 == 0 and s[last_ind] == '1' or (temp % 2 == 1 and s[last_ind] == '0'):
					ans[i] = ans[last_ind] + i - last_ind
				else:
					ans[i] += i - last_ind
			last_ind = i
		else:
			if last_ind == -1:
				ans[i] += i + 1
			else:
				temp = i - last_ind - 1
				if temp % 2 == 0 and s[last_ind] == '0' or (temp % 2 == 1 and s[last_ind] == '1'):
					ans[i] = ans[last_ind] + i - last_ind
				else:
					ans[i] += i - last_ind
			last_ind = i
	print(sum(ans))


from sys import stdin, stdout
intn = lambda : int(stdin.readline())
strs = lambda : stdin.readline()[:-1]
lstr = lambda : list(stdin.readline()[:-1])
mint = lambda : map(int, stdin.readline().split())
lint = lambda : list(map(int, stdin.readline().split()))
out = lambda x: stdout.write(str(x) + '\n')
out_ = lambda x: stdout.write(str(x) + ' ')

def main():
	for _ in range(intn()):
		s = strs()
		n = len(s)
		t = [[0] * 2 for i in range(n + 1)]
		c = 0
		for i in range(n):
			if s[i] == '0':
				t[i][0] = 1 + t[i - 1][1]
				t[i][1] = 0
			elif s[i] == '1':
				t[i][1] = 1 + t[i - 1][0]
				t[i][0] = 0
			else:
				t[i][0] = 1 + t[i - 1][1]
				t[i][1] = 1 + t[i - 1][0]
			c += max(t[i][0], t[i][1])
		out(c)
main()


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(str, input().split())
t = int(input())
for _ in range(t):
	s = list(input())
	n = len(s)
	l = []
	ans = 0
	prev = '?'
	i = 0
	q = 0
	c = 0
	while i < n:
		if s[i] == '?':
			q += 1
		else:
			if q & 1 == 0:
				if s[i] != prev or prev == '?':
					c += q
					c += 1
				else:
					c += q
					ans += c * (c + 1) // 2
					ans -= q * (q + 1) // 2
					c = q + 1
			elif s[i] == prev or prev == '?':
				c += q
				c += 1
			else:
				c += q
				ans += c * (c + 1) // 2
				ans -= q * (q + 1) // 2
				c = q + 1
			q = 0
			prev = s[i]
		i += 1
	c += q
	ans += c * (c + 1) // 2
	print(ans)


from collections import Counter

def unstable(s):
	P = [None if c == '?' else (c == '1') == i % 2 for (i, c) in enumerate(s)]
	q = 0
	k = 0
	r = None
	u = 0
	for p in P:
		if p is None:
			q += 1
			k += 1
		elif p == r:
			q = 0
			k += 1
		else:
			u += k * (k + 1) // 2
			u -= q * (q + 1) // 2
			k = q + 1
			q = 0
			r = p
	u += k * (k + 1) // 2
	return u

def main():
	t = readint()
	print('\n'.join(map(str, (unstable(input()) for _ in range(t)))))
import sys

def readint():
	return int(input())

def readinti():
	return map(int, input().split())

def readintt():
	return tuple(readinti())

def readintl():
	return list(readinti())

def readinttl(k):
	return [readintt() for _ in range(k)]

def readintll(k):
	return [readintl() for _ in range(k)]

def log(*args, **kwargs):
	print(*args, **kwargs, file=sys.stderr)
main()


import sys
input = sys.stdin.readline

def solve():
	s = list(input().strip())
	n = len(s)
	leftmost = [-1] * n
	left = float('inf')
	for i in range(n):
		if s[i] == '?':
			left = min(left, i) if left >= 0 else i
		elif left >= 0:
			leftmost[i] = left
			left = -1
	idx = 0
	while idx < n and s[idx] == '?':
		idx += 1
	if idx == n:
		return n * (n + 1) // 2
	else:
		s[0] = s[idx] if idx % 2 == 0 else str(int(s[idx]) ^ 1)
	ans = cnt = 1
	for i in range(1, n):
		if s[i] == '?':
			s[i] = int(s[i - 1]) ^ 1
			cnt += 1
			ans += cnt
		elif int(s[i - 1]) ^ int(s[i]) == 1:
			cnt += 1
			ans += cnt
		elif leftmost[i] >= 0:
			cnt = i - leftmost[i] + 1
			ans += cnt
		else:
			cnt = 1
			ans += 1
	return ans
for _ in range(int(input())):
	print(solve())


for i in range(int(input())):
	s = input()
	h = [-1] * 2
	ans = 0
	for i in range(len(s)):
		if s[i] == '0' or s[i] == '1':
			h[i % 2 ^ int(s[i])] = i
		q = min(h)
		ans += i - q
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	a = 0
	b = 0
	c = 0
	d = 0
	for char in s:
		if char == '0':
			b = c + 1
			c = 0
			d = b + c
		elif char == '1':
			c = b + 1
			b = 0
			d = b + c
		else:
			(b, c) = (c + 1, b + 1)
			d = d + 1
		a = a + d
	print(a)


t = int(input())
while t > 0:
	t = t - 1
	s = str(input())
	n = len(s)
	s1 = [-1] * n
	s2 = [-1] * n
	k = [0] * n
	for i in range(0, n):
		if s[i] == '0':
			s1[i] = i
		elif i:
			s1[i] = s1[i - 1]
	for i in range(0, n):
		if s[i] == '1':
			s2[i] = i
		elif i:
			s2[i] = s2[i - 1]
	k[0] = 0
	ans = 1
	for i in range(1, n):
		if s[i] == '?':
			k[i] = k[i - 1]
		elif s[i] == '1':
			if s1[i - 1] == s2[i - 1]:
				k[i] = 0
			elif s1[i - 1] > s2[i - 1]:
				x = s1[i - 1]
				if x & 1 != i & 1:
					k[i] = k[x]
				else:
					k[i] = x + 1
			else:
				x = s2[i - 1]
				if x & 1 == i & 1:
					k[i] = k[x]
				else:
					k[i] = x + 1
		elif s1[i - 1] == s2[i - 1]:
			k[i] = 0
		elif s1[i - 1] > s2[i - 1]:
			x = s1[i - 1]
			if x & 1 == i & 1:
				k[i] = k[x]
			else:
				k[i] = x + 1
		else:
			x = s2[i - 1]
			if x & 1 != i & 1:
				k[i] = k[x]
			else:
				k[i] = x + 1
		ans = ans + i - k[i] + 1
	print(ans)


import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
from collections import Counter, deque, defaultdict
from functools import lru_cache, reduce
from heapq import heappush, heappop, heapify, _heappop_max, _heapify_max

def _heappush_max(heap, item):
	heap.append(item)
	heapq._siftdown_max(heap, 0, len(heap) - 1)
from math import gcd as Gcd
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
t = int(readline())
for _ in range(t):
	S = readline().rstrip()
	N = len(S)
	idx = [None] * N
	bound = []
	for i in range(1, N):
		if S[i - 1] != '?':
			idx[i] = i - 1
		else:
			idx[i] = idx[i - 1]
	for i in range(N):
		if idx[i] == None:
			continue
		if S[i] == '?':
			continue
		if (i % 2 == idx[i] % 2) != (S[i] == S[idx[i]]):
			bound.append((idx[i], i + 1))
	(L, R) = ([0], [])
	for (i, j) in bound:
		L.append(i + 1)
		R.append(j - 1)
	R.append(N)
	ans = 0
	for (l, r) in zip(L, R):
		d = r - l + 1
		ans += d * (d - 1) // 2
	for (i, j) in bound:
		d = j - i - 1
		ans -= d * (d - 1) // 2
	print(ans)


import math

def getint():
	return [int(i) for i in input().split()]

def getstr():
	return [str(i) for i in input().split()]

def solve():
	s = input()
	ans = 0
	cnt0 = 0
	cnt1 = 0
	cnt2 = 0
	for i in range(len(s)):
		if s[i] == '1' and i % 2 == 0 or (s[i] == '0' and i % 2 == 1):
			cnt0 += cnt2 + 1
			cnt1 = 0
			cnt2 = 0
		elif s[i] == '0' and i % 2 == 0 or (s[i] == '1' and i % 2 == 1):
			cnt1 += cnt2 + 1
			cnt0 = 0
			cnt2 = 0
		elif s[i] == '?':
			cnt2 += 1
		ans += cnt0 + cnt1 + cnt2
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	s = input()
	k = len(s)
	ans = 0
	x = [-1, -1]
	for i in range(k):
		if s[i] != '?':
			c = int(s[i])
			if c == 0 or c == 1:
				x[c ^ i % 2] = i
		mn = min(x[0], x[1])
		ans += i - mn
	print(ans)


from functools import reduce

def read():
	return list(map(lambda x: int(x), input().split(' ')))
(cas,) = read()
for _ in range(cas):
	s = input()
	r = 0
	ii = -1
	jj = -1
	for (i, c) in enumerate(s):
		if ii == -1:
			if c == '?' or c == '0':
				ii = i
		elif c == '1':
			ii = -1
		if jj == -1:
			if c == '?' or c == '1':
				jj = i
		elif c == '0':
			jj = -1
		if ii == -1:
			r += i - jj + 1
		elif jj == -1:
			r += i - ii + 1
		else:
			r += i - min(ii, jj) + 1
		ii ^= jj
		jj ^= ii
		ii ^= jj
	print(r)


def foo(n):
	return n * (n + 1) // 2
t = int(input())
for tt in range(t):
	s = list(input())
	n = len(s)
	final = 0
	ans = []
	i = 1
	curr = 1
	while i < n:
		if s[i] == '?':
			qlen = 0
			left = s[i - 1]
			while i < n and s[i] == '?':
				qlen += 1
				i += 1
			if i < n and left != '?':
				right = s[i]
				if qlen % 2 and left == right or (qlen % 2 == 0 and left != right):
					curr += qlen
				else:
					final -= foo(qlen)
					ans.append(curr + qlen)
					curr = qlen
			else:
				curr += qlen
		else:
			if s[i] == s[i - 1]:
				ans.append(curr)
				curr = 1
			else:
				curr += 1
			i += 1
	ans.append(curr)
	for i in range(len(ans)):
		final += foo(ans[i])
	print(final)


import sys, os.path
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	s = input()
	n = len(s)
	pos = [-1, -1]
	ans = 0
	for ind in range(n):
		k = -1
		if s[ind] == '0':
			k = 0
		elif s[ind] == '1':
			k = 1
		if k == 0 or k == 1:
			pos[k ^ ind % 2] = ind
		ans += ind - min(pos)
	print(ans)


def calc():
	s = input()
	chk = -1
	buff = 0
	cur = '0'
	ans = 0
	for i in range(len(s)):
		if s[i] == '?':
			buff += 1
			cur = '1' if cur == '0' else '0'
		else:
			if s[i] == cur:
				chk = i - buff - 1
			buff = 0
			cur = s[i]
		ans += i - chk
	print(ans)
t = int(input())
for _i in range(t):
	calc()


import math
t = int(input())
for _ in range(t):
	s = input()
	b = []
	for j in s:
		b.append(j)
	n = len(b)
	s = []
	ans = 1
	dp = [0 for i in range(n)]
	la = 0
	dp[0] = 1
	for j in range(1, n):
		if b[la] == '?':
			dp[j] = j - la + 1
		elif b[j] == '?':
			dp[j] = j - la + dp[la]
		elif (j - la) % 2:
			if b[j] != b[la]:
				dp[j] = dp[la] + (j - la)
			else:
				dp[j] = j - la
		elif b[j] == b[la]:
			dp[j] = dp[la] + (j - la)
		else:
			dp[j] = j - la
		if b[j] != '?':
			la = j
	print(sum(dp))


from math import *
import sys
input = sys.stdin.readline
sys.setrecursionlimit(3 * 10 ** 5)

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	s = st()
	t -= 1
	n = len(s)
	i = 0
	fl = ''
	co = 0
	qc = 0
	r = 0
	ex = 0
	while i < n:
		if s[i] == '?':
			qc += 1
			i += 1
			co += 1
			continue
		if fl == '':
			fl = s[i]
			qc = 0
			co += 1
			i += 1
			continue
		if qc % 2 == 0 and fl != s[i]:
			fl = s[i]
			i += 1
			qc = 0
			co += 1
			continue
		if qc % 2 and fl == s[i]:
			i += 1
			qc = 0
			co += 1
			continue
		r += co * (co + 1) // 2 + ex * co
		co = 1
		if qc:
			ex = qc
		else:
			ex = 0
		fl = s[i]
		qc = 0
		i += 1
	r += co * (co + 1) // 2 + ex * co
	print(r)


def gcd(a, b):
	c = a % b
	while c != 0:
		a = b
		b = c
		c = a % b
	return b
for _ in range(int(input())):
	zoz = list(str(input()))
	res = 0
	p = 0
	for i in range(len(zoz)):
		if zoz[i] == '?' or (zoz[i] == '0' and i % 2 == 0) or (zoz[i] == '1' and i % 2 == 1):
			p += 1
		else:
			res += p * (p + 1) // 2
			p = 0
	res += p * (p + 1) // 2
	p = 0
	for i in range(len(zoz)):
		if zoz[i] == '?' or (zoz[i] == '0' and i % 2 == 1) or (zoz[i] == '1' and i % 2 == 0):
			p += 1
		else:
			res += p * (p + 1) // 2
			p = 0
	res += p * (p + 1) // 2
	p = 0
	for i in range(len(zoz)):
		if zoz[i] == '?':
			p += 1
		else:
			res -= p * (p + 1) // 2
			p = 0
	res -= p * (p + 1) // 2
	print(res)


def main():
	s = input()
	x = 0
	n = len(s)
	ans = 0
	flag = True
	a = [0] * n
	for i in range(1, n):
		if s[i - 1] == '?':
			a[i] = a[i - 1]
		else:
			a[i] = i
	pre = 0
	for i in range(n):
		if s[i] == '0' and flag == True and i % 2:
			flag = False
			x = x + pre
			ans += (x * x + x) // 2 - (pre * pre + pre) // 2
			x = 1
			pre = i - a[i]
		elif s[i] == '0' and flag == False and (i % 2 == 0):
			flag = True
			x = x + pre
			ans += (x * x + x) // 2 - (pre * pre + pre) // 2
			x = 1
			pre = i - a[i]
		elif s[i] == '1' and flag == True and (i % 2 == 0):
			flag = False
			x = x + pre
			ans += (x * x + x) // 2 - (pre * pre + pre) // 2
			x = 1
			pre = i - a[i]
		elif s[i] == '1' and flag == False and i % 2:
			flag = True
			x = x + pre
			ans += (x * x + x) // 2 - (pre * pre + pre) // 2
			x = 1
			pre = i - a[i]
		else:
			x += 1
	x = x + pre
	ans += (x * x + x) // 2 - (pre * pre + pre) // 2
	print(ans)
t = int(input())
for i in range(t):
	main()


for ii in range(int(input())):
	n = input()
	(l, a, b, co) = (len(n), [], [], 1)
	x = [0] * l
	for jj in range(l):
		if n[jj] == '0':
			a.append(jj)
		elif a:
			a.append(a[-1])
		else:
			a.append(-1)
		if n[jj] == '1':
			b.append(jj)
		elif b:
			b.append(b[-1])
		else:
			b.append(-1)
	for jj in range(1, l):
		if n[jj] == '?':
			x[jj] = x[jj - 1]
		elif a[jj - 1] == b[jj - 1]:
			x[jj] = 0
		elif a[jj - 1] > b[jj - 1]:
			kk = a[jj - 1]
			if n[jj] == '0':
				if kk % 2 == jj % 2:
					x[jj] = x[kk]
				else:
					x[jj] = kk + 1
			elif kk % 2 != jj % 2:
				x[jj] = x[kk]
			else:
				x[jj] = kk + 1
		else:
			kk = b[jj - 1]
			if n[jj] == '0':
				if kk % 2 != jj % 2:
					x[jj] = x[kk]
				else:
					x[jj] = kk + 1
			elif kk % 2 == jj % 2:
				x[jj] = x[kk]
			else:
				x[jj] = kk + 1
		co += 1 + jj - x[jj]
	print(co)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7

def ssinp():
	return input()

def iinp():
	return int(input())

def nninp():
	return map(int, input().split())

def llinp():
	return list(map(int, input().split()))

def p(xyz):
	print(xyz)

def p2(a, b):
	print(a, b)
import math
for __ in range(iinp()):
	s = ssinp()
	l = list(s)
	n = len(l)
	ans = ans1 = 0
	curr = l[0]
	cnt = 1
	ques = 0
	if curr == '?':
		ques += 1
	for i in range(1, n):
		if curr == '?':
			if l[i] == '1':
				curr = '0'
			elif l[i] == '0':
				curr = '1'
			else:
				cnt += 1
				ques += 1
		if curr == '1':
			if l[i] == '0' or l[i] == '?':
				cnt += 1
				curr = '0'
				if l[i] == '?':
					ques += 1
				else:
					ques = 0
			else:
				ans += cnt * (cnt + 1) // 2
				cnt = 1 + ques
				ans1 += ques * (ques + 1) // 2
				curr = '1'
				ques = 0
		elif curr == '0':
			if l[i] == '1' or l[i] == '?':
				cnt += 1
				curr = '1'
				if l[i] == '?':
					ques += 1
				else:
					ques = 0
			else:
				ans += cnt * (cnt + 1) // 2
				cnt = 1 + ques
				ans1 += ques * (ques + 1) // 2
				curr = '0'
				ques = 0
	ans += cnt * (cnt + 1) // 2
	print(ans - ans1)


bu = int(input())
for j in range(bu):
	ap = input()
	i = len(ap)
	for az in range(len(ap)):
		if ap[az] != '?':
			i = az + 1
			digit = ap[az]
			count = az + 1
			lastquestionmark = 0
			break
		else:
			pass
	if i == len(ap):
		print(len(ap) * (len(ap) + 1) // 2)
		continue
	ans = len(ap)
	while i < len(ap):
		if ap[i] == '?':
			if ap[i - 1] != '?':
				lastquestionmark = i
				count += 1
				i += 1
				if digit == '1':
					digit = '0'
				else:
					digit = '1'
			else:
				count += 1
				i += 1
				if digit == '1':
					digit = '0'
				else:
					digit = '1'
		elif digit == ap[i]:
			ans = ans + count * (count - 1) // 2
			if ap[i - 1] == '?' and lastquestionmark != i - 1:
				i += 1
				count = i - lastquestionmark
				ans -= (count - 1) * (count - 2) // 2
			elif ap[i - 1] == '?' and lastquestionmark == i - 1:
				count = 2
				i += 1
			else:
				i += 1
				count = 1
		else:
			i += 1
			count += 1
			if digit == '1':
				digit = '0'
			else:
				digit = '1'
	ans += count * (count - 1) // 2
	print(ans)


t = int(input())
for i in range(0, t):
	s = input()
	a = []
	n = len(s)
	pr = s[0]
	q = 0
	arr = []
	k = ''
	if pr == '?':
		before = '54'
		q += 1
		start = True
	else:
		start = False
	k += s[0]
	for i in range(1, n):
		if s[i] != '?' and q > 0:
			if before == s[i] and q % 2 == 1 or start:
				k += s[i]
			elif before != s[i] and q % 2 == 0 or start:
				k += s[i]
			else:
				a.append(k)
				k = '?' * q + s[i]
				arr.append(q)
			q = 0
			start = False
		elif s[i] == '?' and q == 0:
			before = s[i - 1]
			q += 1
			k += '?'
		elif s[i] == '?' and q > 0:
			q += 1
			k += '?'
		elif s[i] == s[i - 1]:
			a.append(k)
			k = s[i]
		else:
			k += s[i]
	a.append(k)
	ans = 0
	for i in range(0, len(arr)):
		k = arr[i]
		kk = k * (k + 1) // 2
		ans -= kk
	for i in range(0, len(a)):
		s = a[i]
		k = len(s)
		if k > 0:
			kk = k * (k + 1) // 2
			ans += kk
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = input()
	last = -1
	total = 0
	qn = 0
	currLen = 0
	for i in range(len(n)):
		if n[i] == '?':
			currLen += 1
			qn += 1
		elif last == -1:
			last = n[i]
			currLen += 1
			qn = 0
		elif last == '1' and qn % 2 == 1 and (n[i] == '1'):
			currLen += 1
			qn = 0
		elif last == '0' and qn % 2 == 1 and (n[i] == '0'):
			currLen += 1
			qn = 0
		elif last == '1' and qn % 2 == 0 and (n[i] == '0'):
			currLen += 1
			qn = 0
			last = '0'
		elif last == '0' and qn % 2 == 0 and (n[i] == '1'):
			currLen += 1
			qn = 0
			last = '1'
		else:
			total += currLen * (currLen - 1) // 2 - qn * (qn - 1) // 2
			last = n[i]
			currLen = qn + 1
			qn = 0
	total = total + currLen * (currLen - 1) // 2
	print(total + len(n))


for _ in range(int(input())):
	s = input()
	n = len(s)
	z = [0] * n
	o = [0] * n
	if s[n - 1] == '0':
		z[n - 1] = 1
	elif s[n - 1] == '1':
		o[n - 1] = 1
	else:
		z[n - 1] = 1
		o[n - 1] = 1
	ans = 0
	ans += max(z[n - 1], o[n - 1])
	for i in range(n - 2, -1, -1):
		if s[i] == '0':
			z[i] = 1 + o[i + 1]
		elif s[i] == '1':
			o[i] = 1 + z[i + 1]
		else:
			z[i] = 1 + o[i + 1]
			o[i] = 1 + z[i + 1]
		ans += max(z[i], o[i])
	print(ans)


def solve():
	s = input()
	dp = [1] * len(s)
	prev = s[0]
	counter = 1 if prev == '?' else 0
	for i in range(1, len(s)):
		if s[i] == '?':
			dp[i] += dp[i - 1]
			counter += 1
		if s[i] == '1':
			if prev == '?':
				dp[i] += counter
			if prev == '0' and counter % 2 == 0:
				dp[i] += dp[i - 1]
			if prev == '1' and counter % 2 == 0 and (counter > 0):
				dp[i] += counter
			if prev == '1' and counter % 2 != 0:
				dp[i] += dp[i - 1]
			if prev == '0' and counter % 2 != 0:
				dp[i] += counter
			counter = 0
			prev = s[i]
		if s[i] == '0':
			if prev == '?':
				dp[i] += counter
			if prev == '1' and counter % 2 == 0:
				dp[i] += dp[i - 1]
			if prev == '0' and counter % 2 == 0 and (counter > 0):
				dp[i] += counter
			if prev == '0' and counter % 2 != 0:
				dp[i] += dp[i - 1]
			if prev == '1' and counter % 2 != 0:
				dp[i] += counter
			counter = 0
			prev = s[i]
	return sum(dp)
t = int(input())
while t > 0:
	t -= 1
	print(solve())


from queue import PriorityQueue
from queue import Queue
import math
from collections import *
import sys
import operator as op
from functools import reduce
MOD = int(1000000000.0 + 7)
input = sys.stdin.readline

def ii():
	return list(map(int, input().strip().split()))

def ist():
	return input().strip().split()
for _ in range(int(input())):
	s = input().strip()
	(n, pre) = (len(s), s[0])
	res = [0] * n
	res[0] = 1
	c = 1 if pre == '?' else 0
	for k in range(1, n):
		if pre == s[k]:
			res[k] = 1 + c
		else:
			res[k] = res[k - 1] + 1
		if s[k] == '?':
			c += 1
			if pre != '?':
				pre = '0' if pre == '1' else '1'
		else:
			(c, pre) = (0, s[k])
	print(sum(res))


from sys import stdin as sin

def aint():
	return int(input())

def amap():
	return map(int, sin.readline().split())

def alist():
	return list(map(int, sin.readline().split()))

def astr():
	return input()
for _ in range(aint()):
	s = input()
	n = len(s)
	d = [False] * n
	for i in range(n):
		if s[i] == '?':
			d[i] = True
	l = list(s)
	r = [0] * n
	ans = 0
	m = 0
	for i in range(n):
		if l[i] == '0':
			if i == 0:
				r[i] += 1
			elif l[i - 1] == '1' and (not d[i - 1]):
				r[i] += r[i - 1] + 1
			elif l[i - 1] == '1' and d[i - 1]:
				r[i] += r[i - 1] + 1
			elif d[i - 1]:
				r[i] = m + 1
			else:
				r[i] += 1
			m = 0
		elif l[i] == '1':
			if i == 0:
				r[i] += 1
			elif l[i - 1] == '0' and (not d[i - 1]):
				r[i] += r[i - 1] + 1
			elif l[i - 1] == '0' and d[i - 1]:
				r[i] += r[i - 1] + 1
			elif d[i - 1]:
				r[i] = m + 1
			else:
				r[i] += 1
			m = 0
		else:
			if i == 0:
				r[i] += 1
			elif l[i - 1] == '0' and (not d[i - 1]):
				l[i] = '1'
				r[i] += r[i - 1] + 1
			elif l[i - 1] == '1' and (not d[i - 1]):
				l[i] = '0'
				r[i] += r[i - 1] + 1
			elif l[i - 1] == '?':
				r[i] += m + 1
			elif l[i - 1] == '1':
				l[i] = '0'
				r[i] += r[i - 1] + 1
			else:
				l[i] = '1'
				r[i] += r[i - 1] + 1
			m += 1
		ans += r[i]
	print(ans)


import sys
import math
import random
import heapq
input = sys.stdin.readline

def pow(a, n, m):
	if n == 0:
		return 1
	x = pow(a, n // 2, m)
	if n % 2 == 0:
		return x * x % m
	else:
		return x * x * a % m

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
t = int(input())
while t > 0:
	s = input().strip()
	dp = [[0, 0] for i in range(len(s))]
	if s[0] == '0':
		dp[0][0] = 1
	elif s[0] == '1':
		dp[0][1] = 1
	else:
		dp[0][0] = 1
		dp[0][1] = 1
	l = -1
	b = 0
	for i in range(1, len(s)):
		if s[i] == '0':
			dp[i][0] = dp[i - 1][1] + 1
		elif s[i] == '1':
			dp[i][1] = dp[i - 1][0] + 1
		else:
			dp[i][0] = dp[i - 1][1] + 1
			dp[i][1] = dp[i - 1][0] + 1
	ans = 0
	for i in dp:
		ans += max(i[0], i[1])
	print(ans)
	t -= 1


for s in [*open(0)][1:]:
	r = p = i = j = k = 0
	for x in s[:-1]:
		i += 1
		x = ord(x) ^ i & 1
		if p != x < 50:
			p = x
			k = j
		r += i - k
		j = (j, i)[x < 50]
	print(r)


import math
from collections import Counter, defaultdict
import sys
mod = 10 ** 9 + 7
input = sys.stdin.readline
readInt = lambda : int(input().strip())
readfloat = lambda : float(input().strip())
readStr = lambda : input().strip()
intList = lambda : list(map(int, input().strip().split()))
intMap = lambda : map(int, input().strip().split())
floatList = lambda : list(map(float, input().strip().split()))
floatMap = lambda : map(float, input().strip().split())
strList = lambda : list(input().strip().split())

def print(*args, end='\n', sep=' '):
	for i in args:
		sys.stdout.write(str(i))
		sys.stdout.write(sep)
	sys.stdout.write(end)

def solve(s):
	n = len(s)
	dp = [1] * n
	prev = s[0]
	qlen = 0
	if s[0] == '?':
		qlen = 1
	for i in range(1, n):
		if s[i] == '1':
			if i - qlen - 1 >= 0:
				if qlen & 1 == 0 and s[i - qlen - 1] == '0' or (qlen & 1 and s[i - qlen - 1] == '1'):
					dp[i] += dp[i - qlen - 1] + qlen
				else:
					dp[i] += qlen
			else:
				dp[i] += dp[i - 1]
			qlen = 0
		elif s[i] == '0':
			if i - qlen - 1 >= 0:
				if qlen & 1 == 0 and s[i - qlen - 1] == '1' or (qlen & 1 and s[i - qlen - 1] == '0'):
					dp[i] += dp[i - qlen - 1] + qlen
				else:
					dp[i] += qlen
			else:
				dp[i] += dp[i - 1]
			qlen = 0
		else:
			dp[i] += dp[i - 1]
			qlen += 1
	return sum(dp)
for _ in range(readInt()):
	s = list(input().strip())
	print(solve(s))


import math
for _ in range(int(input())):
	n = input()
	b = 0
	c = n[0]
	count = 1
	q_count = 0
	re = 0
	if n[0] == '?':
		q_count += 1
	for i in range(1, len(n)):
		if n[i] == '?':
			count += 1
			q_count += 1
		elif b % 2 == i % 2 and c == n[i] or (b % 2 != i % 2 and c != n[i]) or c == '?':
			count += 1
		else:
			re += count * (count + 1) // 2
			if n[i - 1] == '?':
				count = q_count + 1
				re -= q_count * (q_count + 1) // 2
			else:
				count = 1
		if n[i] != '?':
			q_count = 0
			b = i
			c = n[i]
	if count > 0:
		re += count * (count + 1) // 2
	print(re)


import sys
input = sys.stdin.readline
from collections import deque
t = int(input())
for tests in range(t):
	S = input().strip()
	ANS = 0
	Q = deque()
	p = 0
	LEN = len(S)
	NEXT = -1
	ques = 0
	while True:
		if p < LEN:
			if len(Q) == 0:
				Q.append(S[p])
				if S[p] == '0':
					NEXT = 1
				elif S[p] == '1':
					NEXT = 0
				else:
					ques = 1
				p += 1
				continue
			elif S[p] == '?':
				Q.append(S[p])
				if NEXT != -1:
					NEXT ^= 1
				ques += 1
				p += 1
				continue
			elif S[p] == str(NEXT) or NEXT == -1:
				Q.append(S[p])
				if NEXT == -1:
					if S[p] == '0':
						NEXT = 1
					elif S[p] == '1':
						NEXT = 0
				else:
					NEXT ^= 1
				p += 1
				ques = 0
				continue
			else:
				while len(Q) > ques:
					ANS += len(Q)
					Q.popleft()
				NEXT = -1
		elif len(Q) == 0:
			break
		else:
			ANS += len(Q)
			Q.popleft()
	print(ANS)


import math
T = int(input())
for _ in range(T):
	s = input()
	n = len(s)
	mm = -1
	ans = 0
	par = [-1, -1]
	last = [-1, -1]
	for i in range(0, n):
		if s[i] != '?':
			p = (int(s[i]) + i) % 2
			last[p] = i
			par[p] = last[p ^ 1]
		mm = max(par[0], par[1])
		ans += i - mm
	print(ans)


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, gcd, log
import bisect
import sys
import copy

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	s = input()
	n = len(s)
	ind = 1
	st = 0
	mid = st
	last_seen = s[0]
	ans = 0
	while ind < n:
		if last_seen != s[ind]:
			if s[ind] == '?':
				if last_seen == '0':
					last_seen = '1'
				elif last_seen == '1':
					last_seen = '0'
			else:
				last_seen = s[ind]
		elif s[ind - 1] == s[ind] == '?':
			pass
		elif s[ind] == s[ind - 1]:
			k = ind - st
			ans += k * (k + 1) // 2
			st = ind
			mid = ind
		else:
			k = mid - st
			l = ind - mid + 1
			r = ind - st
			ans += k * (l + r) // 2
			st = mid
		if s[ind] == '?' and s[ind - 1] != '?':
			mid = ind
		ind += 1
	k = ind - st
	ans += k * (k + 1) // 2
	print(ans)


t = int(input())
smth = '01'
for i in range(t):
	c = input()
	n = len(c)
	p1 = 0
	p2 = 0
	counter = 0
	while p2 < n:
		if c[p1] == smth[(p1 + 1) % 2]:
			p1 += 1
			if p1 > p2:
				p2 += 1
		else:
			while p2 < n and c[p2] != smth[(p2 + 1) % 2]:
				p2 += 1
			counter += (p2 - p1) * (p2 - p1 + 1) / 2
			p1 = p2
	p1 = 0
	p2 = 0
	while p2 < n:
		if c[p1] == smth[p1 % 2]:
			p1 += 1
			if p1 > p2:
				p2 += 1
		else:
			while p2 < n and c[p2] != smth[p2 % 2]:
				p2 += 1
			counter += (p2 - p1) * (p2 - p1 + 1) / 2
			p1 = p2
	p1 = 0
	p2 = 0
	while p2 < n:
		if c[p1] != '?':
			p1 += 1
			if p1 > p2:
				p2 += 1
		else:
			while p2 < n and c[p2] == '?':
				p2 += 1
			counter -= (p2 - p1) * (p2 - p1 + 1) / 2
			p1 = p2
	print(int(counter))


def solve():
	N = len(A)
	dp = [[0, 0] for i in range(N)]
	for i in range(N):
		if A[i] == '1' or A[i] == '?':
			dp[i][1] = (dp[i - 1][0] if i > 0 else 0) + 1
		if A[i] == '0' or A[i] == '?':
			dp[i][0] = (dp[i - 1][1] if i > 0 else 0) + 1
	ans = 0
	for i in range(N):
		ans += dp[i][0] + dp[i][1]
		if A[i] == '?':
			ans -= min(dp[i])
	return ans
test_cases = int(input())
for test_case in range(test_cases):
	A = input()
	print(solve())


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def Solution(s):
	c0 = 0
	c1 = 0
	ans = 0
	for c in s:
		if c == '0':
			c0 += 1
			c1 = 0
			ans += c0
		elif c == '1':
			c1 += 1
			c0 = 0
			ans += c1
		else:
			c0 += 1
			c1 += 1
			ans += max(c0, c1)
		tmp = c0
		c0 = c1
		c1 = tmp
	print(ans)

def main():
	for _ in range(get_int()):
		Solution(get_string())
main()


from io import BytesIO, IOBase
import sys
import math
import os
import heapq
from collections import defaultdict, deque
from math import ceil
from bisect import bisect_left, bisect_left
from time import perf_counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def mint():
	return map(int, input().split())

def mfloat():
	return map(float, input().split())

def intin():
	return int(input())

def solve():
	s = input()
	ans = 0
	n = len(s)
	start_pair = [-1, -1]
	for i in range(n):
		if s[i] != '?':
			idx = i
			start_pair = [0, s[i] if i % 2 == 0 else str(1 - int(s[i]))]
			break
	if start_pair[0] == -1:
		print(n * (n + 1) // 2)
		return
	current_pair = start_pair.copy()
	for (idx, i) in enumerate(s):
		if i in '01':
			if (idx - current_pair[0]) % 2 and i != current_pair[1] or ((idx - current_pair[0]) % 2 == 0 and i == current_pair[1]):
				(current_pair[0], current_pair[1]) = (idx, i)
			else:
				length = idx - start_pair[0]
				ans += length * (length + 1) // 2
				(start_pair[0], start_pair[1]) = (current_pair[0] + 1, current_pair[1])
				overlap = idx - current_pair[0] - 1
				ans -= overlap * (overlap + 1) // 2
				(current_pair[0], current_pair[1]) = (idx, i)
	length = n - start_pair[0]
	ans += length * (length + 1) // 2
	print(ans)

def main():
	t = int(input())
	for _ in range(t):
		solve()
start_time = perf_counter()
main()
print(perf_counter() - start_time, file=sys.stderr)


def solve(s):
	res = 0
	(pos0, pos1) = (0, 0)
	for c in s:
		if c == '0':
			pos0 += 1
			pos1 = 0
			res += pos0
		elif c == '1':
			pos1 += 1
			pos0 = 0
			res += pos1
		else:
			pos1 += 1
			pos0 += 1
			res += max(pos1, pos0)
		(pos1, pos0) = (pos0, pos1)
	return res
t = int(input())
while t:
	t -= 1
	s = str(input())
	print(solve(s))


import re
g = lambda p: sum((l * l + l >> 1 for l in map(len, re.split(p, t))))
for s in [*open(0)][1:]:
	t = ''
	f = 0
	for x in s[:-1]:
		t += chr(ord(x) ^ f)
		f ^= 1
	print(g('0') + g('1') - g('0|1'))


from sys import stdin, stderr
input = stdin.readline

def dbp(*args, **kwargs):
	print(*args, file=stderr, **kwargs)

def get_int_list():
	return [int(x) for x in input().strip().split()]

def beautiful(s):
	pol = None
	for (idx, c) in enumerate(s):
		if pol == None:
			if c == '0':
				pol = idx % 2
			elif c == '1':
				pol = (idx + 1) % 2
		elif c == '0':
			if idx % 2 != pol:
				return False
		elif c == '1':
			if (idx + 1) % 2 != pol:
				return False
	return True

def slow_solve(s):
	n = len(s)
	count = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			sub = s[i:j]
			dbp(sub, end=' ')
			if beautiful(sub):
				dbp('beautiful')
				count += 1
			else:
				dbp('nope')
				break
	dbp('final')
	return count

def med_solve(s):
	odds = evens = total = 0
	for (idx, c) in enumerate(s):
		if idx % 2 == 0:
			if c == '1':
				odds += 1
				evens = 0
				total += odds
			elif c == '0':
				evens += 1
				odds = 0
				total += evens
			else:
				assert c == '?'
				evens += 1
				odds += 1
				total += max(odds, evens)
		else:
			assert idx % 2 == 1
			if c == '0':
				odds += 1
				evens = 0
				total += odds
			elif c == '1':
				evens += 1
				odds = 0
				total += evens
			else:
				assert c == '?'
				evens += 1
				odds += 1
				total += max(odds, evens)
	return total

def do_thing():
	s = input().strip()
	r = med_solve(s)
	return r

def multicase():
	maxcc = int(input().strip())
	for cc in range(maxcc):
		print(do_thing())
multicase()


for _ in range(int(input())):
	s = input()
	n = len(s)
	last = s[0]
	last_bit = s[0] if s[0] != '?' else 'x'
	longest_bs = 1
	longest_qm = 1 if last == '?' else 0
	cnt = 0
	for i in range(1, n):
		if s[i] == '1':
			if last == '0':
				longest_bs += 1
			elif last == '1':
				cnt += longest_bs * (longest_bs + 1) // 2
				longest_bs = 1
			elif last_bit == '0':
				if longest_qm % 2 == 1:
					cnt += longest_bs * (longest_bs + 1) // 2
					cnt -= longest_qm * (longest_qm + 1) // 2
					longest_bs = 1 + longest_qm
					longest_qm = 0
				else:
					longest_bs += 1
					longest_qm = 0
			elif longest_qm % 2 == 1:
				longest_bs += 1
				longest_qm = 0
			else:
				cnt += longest_bs * (longest_bs + 1) // 2
				cnt -= longest_qm * (longest_qm + 1) // 2
				longest_bs = 1 + longest_qm
				longest_qm = 0
		elif s[i] == '0':
			if last == '1':
				longest_bs += 1
			elif last == '0':
				cnt += longest_bs * (longest_bs + 1) // 2
				longest_bs = 1
			elif last_bit == '1':
				if longest_qm % 2 == 1:
					cnt += longest_bs * (longest_bs + 1) // 2
					cnt -= longest_qm * (longest_qm + 1) // 2
					longest_bs = 1 + longest_qm
					longest_qm = 0
				else:
					longest_bs += 1
					longest_qm = 0
			elif longest_qm % 2 == 1:
				longest_bs += 1
				longest_qm = 0
			else:
				cnt += longest_bs * (longest_bs + 1) // 2
				cnt -= longest_qm * (longest_qm + 1) // 2
				longest_bs = 1 + longest_qm
				longest_qm = 0
		elif last == '1':
			longest_bs += 1
			longest_qm = 1
		elif last == '0':
			longest_bs += 1
			longest_qm = 1
		else:
			longest_bs += 1
			longest_qm += 1
		last = s[i]
		last_bit = s[i] if s[i] != '?' else last_bit
	cnt += longest_bs * (longest_bs + 1) // 2
	print(cnt)


import sys
mod = 10 ** 9 + 7

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
for _ in range(n):
	s = input()
	count = pre_count = 0
	q_beg = [-1] * len(s)
	for i in range(len(s)):
		if s[i] == '?':
			if i == 0 or s[i - 1] != s[i]:
				q_beg[i] = i
			elif s[i] == s[i - 1]:
				q_beg[i] = q_beg[i - 1]
	q_end = [-1] * len(s)
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '?':
			if i == len(s) - 1 or s[i + 1] != s[i]:
				q_end[i] = i
			elif s[i] == s[i + 1]:
				q_end[i] = q_end[i + 1]
	i = 0
	while i < len(s):
		if s[i] != '?':
			if s[i] != s[i - 1]:
				pre_count += 1
			else:
				count += pre_count * (pre_count + 1) // 2
				pre_count = 1
			i += 1
		elif q_end[i] == len(s) - 1:
			pre_count += q_end[i] - i + 1
			i = len(s)
		elif (q_end[i] - i + 1) % 2:
			if s[i - 1] == s[q_end[i] + 1]:
				pre_count += q_end[i] - i + 1
				i = q_end[i] + 1
			else:
				count += (pre_count + (q_end[i] - i + 1)) * (pre_count + (q_end[i] - i + 1) + 1) // 2 - (q_end[i] - i + 1) * (q_end[i] - i + 2) // 2
				pre_count = q_end[i] - i + 1
				i = q_end[i] + 1
		elif s[i - 1] == s[q_end[i] + 1]:
			count += (pre_count + (q_end[i] - i + 1)) * (pre_count + (q_end[i] - i + 1) + 1) // 2 - (q_end[i] - i + 1) * (q_end[i] - i + 2) // 2
			pre_count = q_end[i] - i + 1
			i = q_end[i] + 1
		else:
			pre_count += q_end[i] - i + 1
			i = q_end[i] + 1
	count += pre_count * (pre_count + 1) // 2
	print(count)


for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = 0
	cnt = 1
	i = 0
	while i < n:
		while i < n and s[i] == '?':
			ans += cnt
			i += 1
			cnt += 1
		consequitive_q_marks = 0
		j = i
		while j < n:
			if s[j] != '?':
				if (i ^ j) & 1:
					if s[i] == s[j]:
						break
				elif s[i] != s[j]:
					break
				consequitive_q_marks = 0
			else:
				consequitive_q_marks += 1
			ans += cnt
			cnt += 1
			j += 1
		i = j
		cnt = 1
		if i > 0 and s[i - 1] == '?':
			cnt += consequitive_q_marks
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	st = 0
	v = []
	i = 0
	while i < n:
		j = i
		if i + 1 < n and s[i] != '?':
			if s[i + 1] == s[i]:
				v.append((i, i + 1))
			i += 1
			continue
		elif i + 1 == n:
			i += 1
			continue
		while j < n and s[j] == '?':
			j += 1
		if i - 1 < 0 or j == n:
			i = j
			continue
		st = i - 1
		en = j
		cn = j - i
		if cn & 1:
			if s[st] != s[en]:
				v.append((st, en))
		elif s[st] == s[en]:
			v.append((st, en))
		i = j
	st = 0
	v.sort()
	ans = 0
	for x in v:
		ans -= (x[1] - x[0] - 1) * (x[1] - x[0] - 1 + 1) // 2
		ans += (x[1] - 1 - st + 1) * (x[1] - 1 - st + 1 + 1) // 2
		st = x[0] + 1
	ans += (n - 1 - st + 1) * (n - 1 - st + 1 + 1) // 2
	print(ans)


for _ in range(int(input())):
	s = input()
	l = [1, 0]
	score = 0
	for should in l:
		curr = 0
		good = []
		for c in s:
			if c == '?':
				curr += 1
			elif c == str(should):
				curr += 1
			else:
				if curr > 0:
					good.append(curr)
				curr = 0
			should = l[should]
		good.append(curr)
		for g in good:
			score += g * (g + 1) // 2
	qgood = []
	qcurr = 0
	for c in s:
		if c == '?':
			qcurr += 1
		else:
			if qcurr > 0:
				qgood.append(qcurr)
			qcurr = 0
	qgood.append(qcurr)
	for q in qgood:
		score -= q * (q + 1) // 2
	print(score)


for _ in range(int(input())):
	s = input()
	n = len(s)
	n0 = 0
	n1 = 0
	su = 0
	for i in range(n):
		if s[i] == '0':
			n0 += 1
			n1 = 0
			su += n0
		elif s[i] == '1':
			n1 += 1
			n0 = 0
			su += n1
		else:
			n0 += 1
			n1 += 1
			su += max(n0, n1)
		(n0, n1) = (n1, n0)
	print(su)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	if s.count('?') == n:
		print(n * (n + 1) // 2)
		continue
	dp = [0] * n
	if s[0] == '?':
		dp[0] = 1
	for i in range(1, n):
		if s[i] == '?':
			if s[i - 1] == '?':
				dp[i] = dp[i - 1] + 1
			else:
				dp[i] = 1
		elif s[i - 1] == '?':
			dp[i] = dp[i - 1]
	ans = 0
	cnt = 0
	for i in range(n):
		if s[i] != '?':
			pos = i
			break
	i = pos
	while i < n:
		j = i
		x = s[i]
		turn = 0
		while j < n:
			if turn == 0:
				if s[j] == x or s[j] == '?':
					pass
				else:
					break
			if turn == 1:
				if s[j] != x or s[j] == '?':
					pass
				else:
					break
			turn = (turn + 1) % 2
			j = j + 1
		a = dp[i]
		b = j - i
		ans = ans + (a + b) * (a + b + 1) // 2 - a * (a + 1) // 2
		if cnt == 0:
			ans = ans + a * (a + 1) // 2
			cnt = 1
		i = j
	print(ans)


def main():
	t = int(input())
	allans = []
	for _ in range(t):
		s = input()
		n = len(s)
		dp0 = [0] * n
		dp1 = [0] * n
		for (i, x) in enumerate(s):
			if s[i] == '?':
				if i - 1 >= 0:
					dp0[i] = 1 + dp1[i - 1]
					dp1[i] = 1 + dp0[i - 1]
				else:
					dp0[i] = 1
					dp1[i] = 1
			elif s[i] == '0':
				if i - 1 >= 0:
					dp0[i] = 1 + dp1[i - 1]
				else:
					dp0[i] = 1
			elif i - 1 >= 0:
				dp1[i] = 1 + dp0[i - 1]
			else:
				dp1[i] = 1
		cnts = 0
		for i in range(n):
			if s[i] == '?':
				cnts += max(dp0[i], dp1[i])
			else:
				cnts += dp0[i] + dp1[i]
		allans.append(cnts)
	multiLineArrayPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


def f(n):
	return n * (n - 1) // 2 + n
t = int(input())
for i in range(t):
	s = input()
	res = 0
	k = 0
	tok = None
	cnt = 0
	for c in s:
		if not tok and c != '?':
			tok = c
		else:
			if c == tok:
				res += f(k) - f(cnt)
				k = cnt + 1
				cnt = 0
				continue
			tok = '1' if tok == '0' else '0'
		if c == '?':
			cnt += 1
		else:
			cnt = 0
		k += 1
	print(res + f(k))


for _ in range(int(input())):
	s = input()
	lengths = []
	inside = True
	count = 0
	prev = '?'
	qprefix = 0
	double_counts = []
	for c in s:
		if c == '?':
			qprefix += 1
		if prev == '?':
			count += 1
			prev = c
			if c != '?':
				qprefix = 0
		elif c == '1' and prev == '0' or (c == '0' and prev == '1'):
			count += 1
			prev = c
			qprefix = 0
		elif prev == '0' and c == '?':
			count += 1
			prev = '1'
		elif prev == '1' and c == '?':
			count += 1
			prev = '0'
		elif prev == c:
			lengths.append(count)
			count = 1 + qprefix
			double_counts.append(qprefix)
			qprefix = 0
	lengths.append(count)
	print(int(sum([x * (x + 1) / 2 for x in lengths])) - int(sum([x * (x + 1) / 2 for x in double_counts])))


from sys import stdin
import math
t = int(stdin.readline())
for i in range(t):
	s = list(stdin.readline()[:-1])
	n = len(s)
	ans = 0
	dp = [[0, 0] for i in range(n + 1)]
	for i in range(1, n + 1):
		if s[i - 1] != '0':
			dp[i][0] = dp[i - 1][1] + 1
		if s[i - 1] != '1':
			dp[i][1] = dp[i - 1][0] + 1
		ans += max(dp[i][0], dp[i][1])
	print(ans)


import sys
import math

def solve(s):
	break_point = 0
	break_candidate = -1
	last_char = ''
	dp = [0] * len(s)
	for i in range(len(s)):
		if i == 0:
			dp[i] = 1
			last_char = s[i]
			continue
		if break_candidate < 0 and s[i - 1] == '?':
			break_candidate = i - 1
		elif s[i - 1] != '?':
			break_candidate = -1
		if last_char == '?':
			last_char = s[i]
			dp[i] = dp[i - 1] + i + 1 - break_point
		else:
			if last_char != s[i]:
				dp[i] = dp[i - 1] + i + 1 - break_point
			else:
				break_point = i
				if s[i - 1] == '?':
					break_point = break_candidate
				dp[i] = dp[i - 1] + i + 1 - break_point
			if s[i] == '?':
				last_char = str(1 - int(last_char))
			else:
				last_char = s[i]
	return dp[-1]
t = int(sys.stdin.readline().strip())
for i in range(t):
	s = sys.stdin.readline().strip()
	print(solve(s))


t = int(input())
for x in range(t):
	s = input()
	ans = 0
	c0 = 0
	c1 = 0
	prev = 0
	for i in range(0, len(s)):
		if s[i] == str(prev) or s[i] == '?':
			c0 += 1
		else:
			c0 = 0
		if s[i] == str(1 - prev) or s[i] == '?':
			c1 += 1
		else:
			c1 = 0
		ans += max(c0, c1)
		prev = 1 - prev
	print(ans)


t = int(input())

def solve(s):
	n = len(s)
	dp = [1 if s[0] in '0?' else 0, 1 if s[0] in '1?' else 0]
	total = max(dp)
	for i in range(1, n):
		if s[i] == '0':
			dp = [1 + dp[1], 0]
			total += sum(dp)
		elif s[i] == '1':
			dp = [0, 1 + dp[0]]
			total += sum(dp)
		else:
			dp = [1 + dp[1], 1 + dp[0]]
			total += max(dp)
	return total
for test in range(t):
	s = input().strip()
	print(solve(s))


def isFine(x, choice):
	if choice == '?':
		if x == '?':
			return (True, '?')
		elif x == '1':
			return (True, '0')
		else:
			return (True, '1')
	elif choice == '1':
		if x == '?' or x == '1':
			return (True, '0')
		else:
			return (False, '?')
	elif x == '0' or x == '?':
		return (True, '1')
	else:
		return (False, '?')
t = int(input())
for _ in range(t):
	a = input()
	n = len(a)
	if n == 1:
		print(1)
	else:
		choice = '?'
		i = 0
		ans = 0
		count = 0
		check = True
		c = 0
		temp = 0
		while i < n:
			if a[i] == '?':
				if check:
					temp = i
					check = False
			else:
				check = True
			(Fine, choice) = isFine(a[i], choice)
			if Fine:
				count += 1
				i += 1
			else:
				if a[i - 1] == '?':
					p = i - temp
					i = temp
				else:
					p = 0
				c += p * (p + 1) // 2
				ans += count * (count + 1) // 2
				count = 0
		ans += count * (count + 1) // 2 - c
		print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	l = [0] * n
	if s[0] == '?':
		l[0] = 1
	for i in range(1, n):
		if s[i] == '?':
			l[i] = l[i - 1] + 1
	l2 = [0] * n
	count = 1
	l2[0] = 1
	for i in range(1, n):
		if s[i] == '?':
			l2[i] = l2[i - 1] + 1
			count += l2[i]
		elif s[i - 1] == '?':
			if l[i - 1] % 2 == 0:
				if s[i] != s[i - l[i - 1] - 1]:
					l2[i] = l2[i - 1] + 1
					count += l2[i]
				else:
					l2[i] = l[i - 1] + 1
					count += l2[i]
			elif s[i] == s[i - l[i - 1] - 1]:
				l2[i] = l2[i - 1] + 1
				count += l2[i]
			else:
				l2[i] = l[i - 1] + 1
				count += l2[i]
		elif s[i - 1] != s[i]:
			l2[i] = l2[i - 1] + 1
			count += l2[i]
		else:
			l2[i] = 1
			count += l2[i]
	print(count)


import sys

def cmpFunc(a):
	if a % 2 == 0:
		return True
	return False

def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def get_string():
	return sys.stdin.readline().strip()
t = int(get_string())
for _ in range(t):
	s = get_string()
	ans = 1
	cnt = 0
	last = [0, 0]
	if s[0] == '0':
		last = [1, 0]
	elif s[0] == '1':
		last = [0, 1]
	else:
		last = [1, 1]
		cnt = 1
	for i in range(1, len(s)):
		if s[i] == '0':
			cnt = 0
			if s[i - 1] != '0':
				ans += last[1] + 1
				last = [last[1] + 1, 0]
			else:
				ans += 1
				last = [1, 0]
		elif s[i] == '1':
			cnt = 0
			if s[i - 1] != '1':
				ans += last[0] + 1
				last = [0, last[0] + 1]
			else:
				ans += 1
				last = [0, 1]
		else:
			cnt += 1
			if s[i - 1] == '?':
				if last[0] > last[1]:
					ans += last[0] + 1
					last = [cnt, last[0] + 1]
				else:
					ans += last[1] + 1
					last = [last[1] + 1, cnt]
			elif s[i - 1] == '0':
				ans += last[0] + 1
				last = [cnt, last[0] + 1]
			elif s[i - 1] == '1':
				ans += last[1] + 1
				last = [last[1] + 1, cnt]
	print(ans)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output1.txt', 'w')
from heapq import heappop, heappush, heapify
from math import ceil, gcd
for _ in range(int(input())):
	res = 1
	s = input()
	n = len(s)
	l = [0] * n
	s1 = [-1] * n
	s2 = s1.copy()
	for i in range(n):
		if s[i] == '0':
			s1[i] = i
		elif i != 0:
			s1[i] = s1[i - 1]
	for i in range(n):
		if s[i] == '1':
			s2[i] = i
		elif i != 0:
			s2[i] = s2[i - 1]
	for i in range(1, n):
		if s[i] == '?':
			l[i] = l[i - 1]
		elif s[i] == '1':
			if s1[i - 1] == s2[i - 1]:
				l[i] = 0
			elif s1[i - 1] > s2[i - 1]:
				j = s1[i - 1]
				if j & 1 != i & 1:
					l[i] = l[j]
				else:
					l[i] = j + 1
			else:
				j = s2[i - 1]
				if j & 1 == i & 1:
					l[i] = l[j]
				else:
					l[i] = j + 1
		elif s1[i - 1] == s2[i - 1]:
			l[i] = 0
		elif s1[i - 1] > s2[i - 1]:
			j = s1[i - 1]
			if i & 1 == j & 1:
				l[i] = l[j]
			else:
				l[i] = j + 1
		else:
			j = s2[i - 1]
			if j & 1 != i & 1:
				l[i] = l[j]
			else:
				l[i] = j + 1
		res += i - l[i] + 1
	print(res)


from bisect import bisect, bisect_left
from collections import *
from heapq import *
from math import gcd, ceil, sqrt, floor, inf, pi
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def popcnt(x):
	ans = 0
	while x:
		ans += 1
		x &= x - 1
	return ans

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

class UF:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n
		self.size = AI(n, 1)
		self.edge = A(n)

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			self.edge[pu] += 1
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			self.edge[pu] += self.edge[pv] + 1
			self.size[pu] += self.size[pv]
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv
			self.edge[pv] += self.edge[pu] + 1
			self.size[pv] += self.size[pu]

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = AI(n, inf)
	d[s] = 0
	heap = [(0, s)]
	vis = A(n)
	while heap:
		(dis, u) = heappop(heap)
		if vis[u]:
			continue
		vis[u] = 1
		for (v, w) in graph[u]:
			if d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

def michange(a, b):
	d = defaultdict(deque)
	for (i, x) in enumerate(b):
		d[x].append(i)
	order = A(len(a))
	for (i, x) in enumerate(a):
		if not d:
			return -1
		order[i] = d[x].popleft()
	return RP(order)

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = N()
for i in range(t):
	ans = 1
	s = input()
	n = len(s)
	dp = A2(n, 3)
	if s[0] == '0':
		dp[0][0] = 1
	elif s[0] == '1':
		dp[0][1] = 1
	else:
		dp[0][2] = 1
	for i in range(1, n):
		if s[i] == '0':
			dp[i][0] = dp[i - 1][1] + 1 + dp[i - 1][2]
			ans += dp[i][0]
		elif s[i] == '1':
			dp[i][1] = dp[i - 1][0] + 1 + dp[i - 1][2]
			ans += dp[i][1]
		else:
			dp[i][2] = dp[i - 1][2] + 1
			dp[i][1] = dp[i - 1][0]
			dp[i][0] = dp[i - 1][1]
			ans += sum(dp[i])
	print(ans)


from itertools import product
import itertools
import sys
import math
import heapq
from collections import deque
MOD = 1000000000007

def find(parent, i):
	if parent[i] != i:
		parent[i] = find(parent, parent[i])
	return parent[i]

def union(parent, rank, xx, yy):
	x = find(parent, xx)
	y = find(parent, yy)
	if rank[x] > rank[y]:
		parent[y] = x
	elif rank[y] > rank[x]:
		parent[x] = y
	else:
		parent[y] = x
		rank[x] += 1
ans = 0
K = int(sys.stdin.readline().strip())
x = 0
y = 0
for _ in range(K):
	ans = 0
	s = sys.stdin.readline().strip()
	n = len(s)
	lo = 0
	hi = 0
	x = 0
	y = 0
	k = 0
	flag = False
	t = [None, None]
	ans = n
	for hi in range(n):
		if s[hi] == '?':
			continue
		ss = int(s[hi])
		if not flag:
			flag = True
			t[hi % 2] = ss
			t[(hi + 1) % 2] = 1 - ss
			x += 1
		elif t[hi % 2] == ss:
			x += 1
		else:
			kk = hi - lo
			while x > 0:
				ans += hi - lo - 1
				if s[lo] == '?':
					lo += 1
				else:
					lo += 1
					x -= 1
			x = 1
			t[hi % 2] = ss
			t[(hi + 1) % 2] = 1 - ss
	kk = hi + 1 - lo
	ans += (kk - 1) * kk // 2
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	fixed = -1
	ans = 0
	curr = 0
	for i in range(n):
		if i == 0:
			curr = 1
			ans = ans + curr
		elif s[i] == '?':
			curr = curr + 1
			ans = ans + curr
		elif s[i] == '0':
			temp = curr + 1
			if i - temp + 1 > fixed:
				curr = curr + 1
				ans = ans + curr
			elif i % 2 != 0 and fixed % 2 != 0 and (s[fixed] == '0'):
				curr = curr + 1
				ans = ans + curr
			elif i % 2 == 0 and fixed % 2 == 0 and (s[fixed] == '0'):
				curr = curr + 1
				ans = ans + curr
			elif i % 2 == 0 and fixed % 2 != 0 and (s[fixed] == '1'):
				curr = curr + 1
				ans = ans + curr
			elif i % 2 != 0 and fixed % 2 == 0 and (s[fixed] == '1'):
				curr = curr + 1
				ans = ans + curr
			else:
				curr = i - fixed
				ans = ans + curr
		else:
			temp = curr + 1
			if i - temp + 1 > fixed:
				curr = curr + 1
				ans = ans + curr
			elif i % 2 != 0 and fixed % 2 != 0 and (s[fixed] == '1'):
				curr = curr + 1
				ans = ans + curr
			elif i % 2 == 0 and fixed % 2 == 0 and (s[fixed] == '1'):
				curr = curr + 1
				ans = ans + curr
			elif i % 2 == 0 and fixed % 2 != 0 and (s[fixed] == '0'):
				curr = curr + 1
				ans = ans + curr
			elif i % 2 != 0 and fixed % 2 == 0 and (s[fixed] == '0'):
				curr = curr + 1
				ans = ans + curr
			else:
				curr = i - fixed
				ans = ans + curr
		if s[i] != '?':
			fixed = i
	print(ans)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	c = dict(Counter(l))
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	l = list(si())
	n = len(l)
	dp = [[0, 0] for i in range(n + 1)]
	for i in range(1, n + 1):
		if l[i - 1] == '0':
			dp[i][0] = 1 + dp[i - 1][1]
		elif l[i - 1] == '1':
			dp[i][1] = 1 + dp[i - 1][0]
		else:
			dp[i][0] = 1 + dp[i - 1][1]
			dp[i][1] = 1 + dp[i - 1][0]
	ans = 0
	for i in range(1, n + 1):
		if l[i - 1] == '0':
			ans += dp[i][0]
		elif l[i - 1] == '1':
			ans += dp[i][1]
		else:
			ans += max(dp[i])
	print(ans)
t = 1
t = ii()
for _ in range(t):
	solve()


def n(x):
	return x * (x + 1) // 2
t = int(input())
for _ in range(t):
	x = input()
	tmp = [0, 0, 0]
	ans = 0
	for i in range(len(x)):
		if x[i] == '?':
			tmp[0] += 1
			tmp[1] += 1
			tmp[2] += 1
		else:
			j = (int(x[i]) - i) % 2
			nj = (j + 1) % 2
			ans = ans - n(tmp[2]) + n(tmp[nj])
			tmp[nj] = 0
			tmp[2] = 0
			tmp[j] += 1
	ans = ans + n(tmp[0]) + n(tmp[1]) - n(tmp[2])
	print(ans)


tc = int(input())
for _ in range(tc):
	s = input()
	(ans, c, i) = (0, 0, 0)
	if s[0] == '?':
		c += 1
	n = len(s)
	for j in range(1, n):
		if s[j] == '?':
			c += 1
		elif c == 0:
			if s[j] == s[j - 1]:
				l = j - i
				ans += (l * l + l) // 2
				i = j
		else:
			x = j - c - 1
			if not x == -1:
				if c % 2 == 0:
					if s[x] == s[j]:
						l = j - i
						ans += (l * l + l) // 2
						i = x + 1
					else:
						ans += (c * c + c) // 2
				elif s[x] != s[j]:
					l = j - i
					ans += (l * l + l) // 2
					i = x + 1
				else:
					ans += (c * c + c) // 2
			else:
				ans += (c * c + c) // 2
			c = 0
	(count, l) = (0, n - i)
	ans += (l * l + l) // 2
	ans += (c * c + c) // 2
	c = 0
	for i in range(n):
		if s[i] == '?':
			c += 1
		else:
			ans -= (c * c + c) // 2
			c = 0
	ans -= (c * c + c) // 2
	print(ans)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	t = int(input())
	for _ in range(t):
		s = input()
		sol = 0
		cnt = 0
		qrun = 0
		prev = None
		for i in s:
			if i == '?':
				qrun += 1
				cnt += 1
			elif i != prev:
				qrun = 0
				cnt += 1
			else:
				sol += cnt * (cnt + 1) // 2
				sol -= qrun * (qrun + 1) // 2
				cnt = qrun + 1
				qrun = 0
			prev = i if i != '?' else '0' if prev == '1' else '1'
		print(sol + cnt * (cnt + 1) // 2)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math

def fun(a, b):
	return math.gcd(a, b)

def solve(s, n):
	c = 0
	prev = None
	d = {'0': '1', '1': '0'}
	ans = 0
	prev_ans = 0
	i = 0
	while i < n:
		temp = 0
		if s[i] != prev and prev != None:
			ans += prev_ans + 1
			temp += prev_ans + 1
		else:
			ans += c + 1
			temp += c + 1
		prev_ans = temp
		if s[i] == '?':
			c += 1
		else:
			c = 0
		if s[i] != '?':
			prev = s[i]
		elif prev:
			prev = d[prev]
		i += 1
	return ans
for _ in range(int(input())):
	s = input()
	print(solve(s, len(s)))


import sys
from sys import stdin
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	s = stdin.readline()[:-1]
	n = len(s)
	ans = 0
	now = 0
	for i in range(n):
		if i % 2 == 0 and s[i] == '1' or (i % 2 == 1 and s[i] == '0'):
			ans += now * (now + 1) // 2
			now = 0
		else:
			now += 1
	ans += now * (now + 1) // 2
	now = 0
	for i in range(n):
		if i % 2 == 0 and s[i] == '0' or (i % 2 == 1 and s[i] == '1'):
			ans += now * (now + 1) // 2
			now = 0
		else:
			now += 1
	ans += now * (now + 1) // 2
	now = 0
	for i in range(n):
		if s[i] != '?':
			ans -= now * (now + 1) // 2
			now = 0
		else:
			now += 1
	ans -= now * (now + 1) // 2
	ANS.append(str(ans))
print('\n'.join(ANS))


from sys import stdin, stdout

def input():
	return stdin.readline().strip()

def read_int_list():
	return list(map(int, input().split()))

def read_int_tuple():
	return tuple(map(int, input().split()))

def read_int():
	return int(input())

def ans(S):
	ret = 0
	num_0 = 0
	num_1 = 0
	parity_0 = None

	def drop(idx):
		nonlocal num_0, num_1, parity_0
		if idx < 0:
			return
		if S[idx] == '?':
			return
		if S[idx] == '1':
			num_1 -= 1
		if S[idx] == '0':
			num_0 -= 1
		if num_0 + num_1 == 0:
			parity_0 = None

	def ok(idx):
		nonlocal num_0, num_1, parity_0
		if idx >= len(S):
			return False
		if S[idx] == '?':
			return True
		if S[idx] == '0':
			if parity_0 is None:
				return True
			return parity_0 == idx % 2
		if S[idx] == '1':
			if parity_0 is None:
				return True
			return parity_0 == 1 - idx % 2

	def consume(idx):
		nonlocal num_0, num_1, parity_0
		if S[idx] == '?':
			return
		if S[idx] == '0':
			num_0 += 1
			parity_0 = idx % 2
		if S[idx] == '1':
			num_1 += 1
			parity_0 = 1 - idx % 2
	j = -1
	for i in range(len(S)):
		drop(i - 1)
		while ok(j + 1):
			j += 1
			consume(j)
		ret += j - i + 1
	return ret
for _ in range(read_int()):
	print(ans(input()))


import sys
input = sys.stdin.readline

def solution(s):
	n = len(s)
	sol = 0
	arr = ['a' for _ in range(n)]
	for (pos, elem) in enumerate(s):
		if elem == '?':
			arr[pos] = 'b'
		elif (pos + int(elem)) % 2 == 0:
			arr[pos] = 'e'
		else:
			arr[pos] = 'o'
	if set(arr) == set(['b']):
		print((n + 1) * n // 2)
		return
	mid = 0
	while mid < n:
		if arr[mid] != 'e':
			mid += 1
		else:
			right = mid
			while right < n and arr[right] != 'o':
				right += 1
			left = mid
			while left >= 0 and arr[left] != 'o':
				left -= 1
			sol += (right - left) * (right - left - 1) // 2
			mid = right
	mid = 0
	while mid < n:
		if arr[mid] != 'o':
			mid += 1
		else:
			right = mid
			while right < n and arr[right] != 'e':
				right += 1
			left = mid
			while left >= 0 and arr[left] != 'e':
				left -= 1
			sol += (right - left) * (right - left - 1) // 2
			mid = right
	left = 1
	while left < n - 1:
		if arr[left] == 'b':
			right = left
			while right < n - 1 and arr[right] == 'b':
				right += 1
			if arr[left - 1] != arr[right] and 'b' not in [arr[left - 1], arr[right]]:
				sol -= (right - left + 1) * (right - left) // 2
			left = right + 1
		else:
			left += 1
	print(sol)
T = int(input())
for t in range(T):
	s = input().strip()
	solution(s)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)

def ii():
	return map(int, input().split())

def ti():
	return int(input())

def lis():
	return [int(i) for i in input().split()]

def maxSub(a, size):
	best = a[0]
	su = 0
	(start, stop) = (0, 0)
	for i in range(size):
		if su > 0:
			su += a[i]
		else:
			su = a[i]
			temp = i
		if su >= best:
			best = su
			start = temp
			stop = i
	return (best, start, stop)
mod = 1000000007

def mexp(n, m):
	res = 1
	ans = 1
	b = 2
	while n > 0:
		if n & 1:
			ans *= b % mod
		b = b * b % mod
		n = n >> 1
		ans %= mod
	ans -= 1
	while m > 0:
		if m & 1:
			res *= ans % mod
		ans = ans * ans % mod
		m = m >> 1
		res %= mod
	return res
for i in range(ti()):
	s = list(str(input()))
	ind = 0
	for i in range(len(s)):
		if s[i] != '?':
			ind = i
			break
	ans = (ind + 2) * (ind + 1) // 2
	count = ind + 1
	dist = 1
	prev = s[ind]
	qm = 0
	for i in range(ind + 1, len(s)):
		if s[i] == '?':
			count += 1
			ans += count
			dist += 1
			if s[i - 1] != '?':
				qm = i
		elif dist % 2:
			if s[i] != prev:
				count += 1
				ans += count
				prev = s[i]
				dist = 1
			elif s[i - 1] == '?':
				ans += i - qm + 1
				count = i - qm + 1
				prev = s[i]
				dist = 1
			else:
				ans += 1
				count = 1
				prev = s[i]
				dist = 1
		elif s[i] == prev:
			count += 1
			ans += count
			prev = s[i]
			dist = 1
		elif s[i - 1] == '?':
			ans += i - qm + 1
			count = i - qm + 1
			prev = s[i]
			dist = 1
		else:
			ans += 1
			count = 1
			prev = s[i]
			dist = 1
	print(ans)


for _ in [*open(0)][1:]:
	w = q = e = 0
	for i in _[:-1]:
		if i == '0':
			e += 1
			w = 0
		elif i == '1':
			w += 1
			e = 0
		else:
			w += 1
			e += 1
		q += max(e, w)
		(w, e) = (e, w)
	print(q)


def unstable_substrings(S):
	l = 0
	lq = 0
	s = 0
	pos = 0
	simb = '?'
	for i in range(len(S)):
		if S[i] == '?':
			lq += 1
		else:
			if simb != '?' and (i - pos) % 2 != (int(S[i]) - int(simb)) % 2:
				s += l * (l + 1) // 2 - lq * (lq + 1) // 2
				l = lq
			simb = S[i]
			pos = i
			lq = 0
		l += 1
	s += l * (l + 1) // 2
	return s
for i in range(int(input())):
	print(unstable_substrings(input()))


import collections
from math import gcd
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = input()[:-1]
	n = len(s)
	r = 0
	l = 0
	ans = 0
	tmp = -1
	tmp2 = 0
	while l < n and r < n:
		t = -1
		while r < n:
			if s[r] != '?':
				if t == -1:
					if s[r] == '1':
						t = (r + 1) % 2
					else:
						t = r % 2
					continue
				if s[r] == '1' and (r - t) % 2 == 0:
					break
				elif s[r] == '0' and (r - t) % 2 == 1:
					break
				tmp = r
			r += 1
		ans += (r - l) * (r - l + 1) // 2 - tmp2 * (tmp2 + 1) // 2
		l = tmp + 1
		tmp2 = r - l
	print(ans)


def f(s):
	dp = [[0, 0] for i in range(len(s))]
	if s[0] == '1':
		dp[0][1] = 1
	elif s[0] == '0':
		dp[0][0] = 1
	else:
		dp[0] = [1, 1]
	ans = 1
	for i in range(1, len(s)):
		if s[i] == '?':
			dp[i][0] = dp[i - 1][1] + 1
			dp[i][1] = dp[i - 1][0] + 1
			ans += max(dp[i][0], dp[i][1])
			continue
		if s[i] == '0':
			dp[i][0] = dp[i - 1][1] + 1
		if s[i] == '1':
			dp[i][1] = dp[i - 1][0] + 1
		ans += dp[i][0] + dp[i][1]
	return ans
for i in range(int(input())):
	print(f(input()))


inp = int(input())
for _ in range(inp):
	s = input()
	z = 0
	o = 0
	res = 0
	for i in s:
		if i == '0':
			z += 1
			o = 0
			res += z
		elif i == '1':
			o += 1
			z = 0
			res += o
		else:
			o += 1
			z += 1
			res += max(z, o)
		(z, o) = (o, z)
	print(res)


t = int(input())

def number(s):
	n = len(s)
	dp = [[0 for x in range(2)] for _ in range(n)]
	if s[0] == '0':
		dp[0][0] = 1
	elif s[0] == '1':
		dp[0][1] = 1
	else:
		dp[0][1] = 1
		dp[0][0] = 1
	for i in range(1, n):
		if s[i] == '0':
			dp[i][0] = dp[i - 1][1] + 1
		elif s[i] == '1':
			dp[i][1] = dp[i - 1][0] + 1
		else:
			dp[i][0] = dp[i - 1][1] + 1
			dp[i][1] = dp[i - 1][0] + 1
	tot = 0
	for i in range(n):
		tot += max(dp[i][0], dp[i][1])
	return tot
for _ in range(t):
	s = input()
	print(number(s))


for t in range(int(input())):
	s = input()
	n = len(s)
	i = 0
	count = 0
	while i < n:
		start = i
		while i < n and s[i] == '?':
			i += 1
		if i == n:
			count += (i - start) * (i - start + 1) // 2
			break
		c = s[i]
		i += 1
		while i < n:
			c = '0' if c == '1' else '1'
			if s[i] != '?' and s[i] != c:
				break
			i += 1
		count += (i - start) * (i - start + 1) // 2
		if i < n and s[i - 1] == '?':
			end = i
			i -= 1
			while s[i] == '?':
				i -= 1
			i += 1
			count -= (end - i) * (end - i + 1) // 2
	print(count)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	s1 = 0
	s2 = 0
	initialiser = 0
	ans = 0
	for i in range(n):
		if ord(s[i]) - ord('0') == initialiser or s[i] == '?':
			s1 += 1
		else:
			s1 = 0
		if ord(s[i]) - ord('0') == 1 - initialiser or s[i] == '?':
			s2 += 1
		else:
			s2 = 0
		ans += max(s1, s2)
		initialiser = 1 - initialiser
	print(ans)