Ahmed Gafer failed to pass the test, but he got the job because of his friendship with Said and Shahhoud. After working in the kitchen for a while, he blew it. The customers didn't like the food anymore and one day he even burned the kitchen. Now the master Chef is very upset.
Ahmed isn't useful anymore at being a co-Chef, so S&S decided to give him a last chance. They decided to give Ahmed a new job, and make him work as the cashier of the restaurant. Nevertheless, in order not to repeat their previous mistake, they decided to give him a little test to check if his counting skills are good enough for the job. The problem is as follows: 
Given a string A of lowercase English letters, Ahmad was asked to find the number of good substrings.
A substring A[L, R] is good if:

-  The length of the substring is exactly 2 and AL = AR, OR
- The length of the substring is greater than 2,AL = AR and the substring A[L + 1, R - 1] has only one distinct letter.

Anyways, Ahmed struggled trying to find a solution for the problem. Since his mathematical skills are very poor as it turned out, he decided to cheat and contacted you asking for your help. Can you help him in this challenge?

-----Input-----
The first line of the input contains the integer T, indicating the number of test cases.
Each of the following T lines, contains a string A.

-----Output-----
For each test case, output a single line containing a single number, indicating the number of good substrings.

-----Constraints-----

- 1 ≤ T ≤ 100 
- 1 ≤  |A|  ≤ 105 
-  It's guaranteed that the sum of  |A|  over all test cases doesn't exceed 5x105. 

-----Example-----
Input:
2
a
abba

Output:
0
2


-----Explanation-----
Example case 2. The good substrings of abba are: { bb } and { abba }.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Combinatorics

Implementation

Starter code:

Solutions:
for t in range(int(input())):
	s = input()
	n = len(s)
	ans = 0
	temp = []
	l = 0
	count = 1
	current = s[0]
	start = 0
	end = 0
	i = 1
	while i < n:
		if s[i] == current:
			count += 1
			end += 1
		else:
			if count > 0:
				temp.append([start, end])
				l += 1
			count = 1
			current = s[i]
			start = i
			end = i
		i += 1
	if count > 0:
		temp.append([start, end])
		l += 1
	for i in range(l):
		le = temp[i][1] - temp[i][0] + 1
		if le >= 2:
			val = le * (le - 1) // 2
			ans += val
		x = temp[i][0] - 1
		y = temp[i][1] + 1
		if x >= 0 and y < n and (s[x] == s[y]):
			ans += 1
	print(ans)


t = int(input())
while t:
	t -= 1
	a = input()
	i = 0
	n = len(a)
	ans = 0
	i = 0
	while i < n - 1:
		j = i + 1
		while j < n and a[i] == a[j]:
			j += 1
		diff = j - i
		ans += diff * (diff - 1) // 2
		i = j
	b = [a[0]]
	i = 1
	while i < n:
		if b[-1] != a[i]:
			b.append(a[i])
		i += 1
	m = len(b)
	for i in range(m - 2):
		if b[i] == b[i + 2]:
			ans += 1
	print(ans)


for _ in range(int(input())):
	Str = input()
	Str += 'M'
	Table = []
	Length = len(Str)
	Char = Str[0]
	Dist = 1
	st = 0
	end = 0
	for i in range(1, Length):
		if Str[i] != Char:
			Table.append(tuple([st, end]))
			st = i
			end = i
			Dist = 1
			Char = Str[i]
		else:
			Dist += 1
			end = i
	Ans = 0
	num = 0
	for (s, e) in Table:
		num = e - s
		Ans += int(num * (num + 1) / 2)
		Left = s - 1
		Right = e + 1
		if Left >= 0 and Right <= Length - 2:
			if Str[Left] == Str[Right]:
				Ans += 1
	print(Ans)


from string import ascii_lowercase as lower
cases = int(input())

def same(s):
	f = s[0]
	for char in s:
		if char != f:
			return False
	return True
for _ in range(cases):
	string = '@' + input() + '#'
	if len(string) == 2:
		print(0)
		continue
	count = 0
	same_since = 1
	prev = string[1]
	for index in range(1, len(string)):
		if string[index] == prev:
			continue
		if string[index] == string[same_since - 1]:
			count += 1
		if index > same_since + 1:
			count += (index - same_since) * (index - same_since - 1) / 2
		same_since = index
		prev = string[index]
	print(int(count))


def main():
	t = int(input())
	for T in range(t):
		st = input()
		count = 0
		ctemp = 1
		ci = 0
		ce = 0
		for i in range(1, len(st)):
			if st[i] == st[ci]:
				ce = i
				continue
			else:
				ctemp = ce - ci + 1
				count += int(ctemp * (ctemp - 1) / 2)
				ctemp = 1
				if ci - 1 >= 0 and ce + 1 < len(st):
					if st[ci - 1] == st[ce + 1]:
						count += 1
				ci = i
				ce = i
		ctemp = ce - ci + 1
		count += int(ctemp * (ctemp - 1) / 2)
		print(count)
main()


for _ in range(int(input().strip())):
	s = input().strip()
	total = 0
	first = 0
	last = 0
	c = 1
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			last = i
			c += 1
		else:
			if first != 0:
				if s[i] == s[first - 1]:
					total += 1
			if c > 1:
				total += c * (c - 1) / 2
			first = i
			last = i
			c = 1
	if first != last:
		total += c * (c - 1) / 2
	print(int(total))


for t in range(int(input())):
	s = input()
	size = len(s)
	i = j = 0
	ans = 0
	while i < size:
		while j < size and s[i] == s[j]:
			j += 1
		if j - 1 != i:
			n = j - i
			ans += n * (n - 1) // 2
		if j - i >= 1 and j < size and (i - 1 > -1) and (s[i - 1] == s[j]):
			ans += 1
		i = j
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	if len(s) >= 2:
		i = 0
		ans = 0
		c = 0
		while i < len(s) - 1:
			if s[i] == s[i + 1]:
				i += 1
				ans += 1
				c += 1
			elif i < len(s) - 2:
				ans += c * (c - 1) // 2
				c = 0
				temp = s[i]
				seti = set()
				seti.add(s[i + 1])
				count = 1
				for j in range(i + 2, len(s)):
					if s[j] not in seti:
						if s[j] == temp:
							ans += 1
						break
					else:
						count += 1
				i = j - 1
				if s[i] != s[i + 1]:
					ans += count * (count - 1) // 2
				else:
					ans += count * (count - 1) // 2 - 1
				i = j - 1
			else:
				ans += c * (c - 1) // 2
				i += 1
		if len(set(s)) == 1:
			ans += c * (c - 1) // 2
		print(ans)
	else:
		print(0)


for _ in range(int(input())):
	s = input()
	l = len(s)
	c = 0
	i = 0
	while i < l - 1:
		if i + 1 < l and s[i] == s[i + 1]:
			j = i
			while i + 1 < l and s[i + 1] == s[i]:
				i += 1
			k = i - j
			c += k * (k + 1) / 2
			if j != 0 and i + 1 < l and (s[j - 1] == s[i + 1]):
				c += 1
		elif i != 0 and i + 1 < l and (s[i - 1] == s[i + 1]):
			c += 1
			i += 1
		else:
			i += 1
	print(int(c))


for _ in range(int(input())):
	a = input()
	if len(a) == 1:
		print(0)
		continue
	comp = 0
	cont = 1
	ans = 0
	for i in range(1, len(a)):
		if a[i] == a[comp]:
			cont += 1
			if i == len(a) - 1:
				ans += cont * (cont - 1) // 2
		else:
			ans += cont * (cont - 1) // 2
			if comp != 0 and a[comp - 1] == a[i]:
				ans += 1
			comp = i
			cont = 1
	print(ans)


t = int(input())
for i in range(t):
	s = input()
	c = 0
	j = 0
	while j < len(s) - 1:
		n = s[j]
		k = j + 1
		while k < len(s) and s[k] == n:
			k += 1
		l = k - j
		if j != 0 and k != len(s) and (s[j - 1] == s[k]):
			c += 1
		c += l * (l - 1) // 2
		j = k
	print(c)


t = int(input())
for i in range(t):
	a = input()
	c = 0
	k = 1
	s = a[0]
	n = 0
	while k < len(a):
		if a[k - 1] == a[k]:
			n += 1
		else:
			c += n * (n + 1) // 2
			n = 0
			if a[k] == s:
				c += 1
				s = a[k - 1]
			if a[k] != s:
				s = a[k - 1]
		k += 1
	if n != 0:
		c += n * (n + 1) // 2
	print(c)


for _ in range(int(input())):
	s = input()
	count = 0
	i = 0
	while i < len(s) - 1:
		ch = s[i]
		j = i + 1
		while j < len(s) and s[j] == ch:
			j += 1
		l = j - i
		if i != 0 and j != len(s) and (s[i - 1] == s[j]):
			count += 1
		count += l * (l - 1) // 2
		i = j
	print(count)


for ppp in range(int(input())):
	arr = input()
	total = 0
	lenght = len(arr)
	for i in range(0, lenght - 1):
		if arr[i] == arr[i + 1]:
			total += 1
	i = 0
	while i < lenght - 2:
		first = arr[i]
		second = arr[i + 1]
		third = arr[i + 2]
		if first == second and third == first:
			k = 0
			for j in range(i + 3, lenght):
				if arr[j] == first:
					k += 1
				else:
					break
			i = i + 2 + k - 1
			tot = 3 + k - 2
			total = total + tot * (tot + 1) // 2
		elif first != second and second == third:
			k = 0
			ans = 0
			for j in range(i + 3, lenght):
				if arr[j] == third:
					k += 1
				elif arr[j] == first:
					ans = 1
					break
				else:
					break
			if ans == 1:
				i = i + 2 + k
				tot = k
				total = total + k * (k + 1) // 2
				total += 1
			else:
				i = i + 2 + k
				total = total + k * (k + 1) // 2
		elif first == second and third != first:
			i += 1
		elif first != second and first == third:
			total += 1
			i += 1
		elif first != second and second != third:
			i = i + 1
	print(total)


t = int(input())
while t > 0:
	t = t - 1
	a = input()
	if len(a) == 1:
		print(0)
		continue
	ans = 0
	prev = a[0]
	op = a[0]
	ctr = 0
	for i in range(1, len(a)):
		curr = a[i]
		if prev == curr:
			ctr += 1
		else:
			ans += ctr * (ctr + 1) // 2
			ctr = 0
			if curr == op:
				ans += 1
			op = prev
		prev = curr
	ans += ctr * (ctr + 1) // 2
	print(ans)


for _ in range(int(input())):
	a = input()
	if len(a) == 2:
		if a[0] == a[1]:
			print(1)
		else:
			print(0)
	elif len(a) < 2:
		print(0)
	else:
		i = 1
		b = a[0]
		c = []
		j = 0
		a += '$'
		while i < len(a):
			if a[i] != b:
				c.append([j, i - 1])
				b = a[i]
				j = i
			i += 1
		count = 0
		for j in c:
			if j[0] > 0 and a[j[0] - 1] == a[j[1] + 1] and (j[1] + 1 < len(a)):
				count += 1
			count += (j[1] - j[0]) * (j[1] - j[0] + 1) // 2
		print(count)


def minimize(arr):
	s = arr[0]
	f = [1]
	for i in arr[1:]:
		if i == s[-1]:
			f[-1] += 1
		else:
			s += i
			f.append(1)
	return tuple((s, f))
t = int(input())
while t > 0:
	t -= 1
	a = input().strip()
	(s, f) = minimize(a)
	val = int(sum([(x - 1) * x / 2 for x in f if x > 1]))
	for i in range(len(s)):
		if i + 2 < len(s) and s[i + 2] == s[i]:
			val += 1
	print(val)


t = int(input())
for i in range(t):
	a = input()
	if len(a) == 1:
		print(0)
		continue
	b = []
	c = []
	z = a[0]
	count = 1
	for j in range(1, len(a)):
		if a[j] == z:
			count += 1
		else:
			b.append(count)
			c.append(z)
			z = a[j]
			count = 1
	b.append(count)
	c.append(z)
	ans = 0
	for j in range(len(b)):
		if b[j] == 2:
			ans += 1
		elif b[j] > 2:
			ans += b[j] * (b[j] - 1) // 2
	for j in range(len(b) - 2):
		if c[j] == c[j + 2]:
			ans += 1
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	s = input()
	i = 0
	ans = 0
	ln = len(s)
	while i < ln:
		l = i
		if i < ln - 1:
			while True:
				if i >= ln - 1 or not s[i] == s[i + 1]:
					break
				i += 1
		u = i
		d = u - l + 1
		ans += (d - 1) * d // 2
		if l > 0 and u < ln - 1:
			if s[l - 1] == s[u + 1]:
				ans += 1
		i = i + 1
	print(ans)


e = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	s = input()
	ans = 0
	n = len(s)
	i = 1
	m = 1
	while i < n and s[i] == s[i - 1]:
		m += 1
		i += 1
	ans += m * (m - 1) // 2
	while i < n:
		x = s[i - 1]
		i += 1
		m = 1
		while i < n and s[i] == s[i - 1]:
			m += 1
			i += 1
		ans += m * (m - 1) // 2
		if i != n and s[i] == x:
			ans += 1
	print(ans)


def nC2(num):
	if num >= 2:
		return int(num * (num - 1) / 2)
	else:
		return 0
t = int(input())
for x in range(t):
	string = input()
	n = len(string)
	goodsubs = 0
	dupcountr = 0
	dupindexL = 0
	dupindexR = 0
	tmpvar = string[0]
	for i in range(n):
		if string[i] == tmpvar:
			dupcountr += 1
		else:
			dupindexR = i - 1
			if dupcountr >= 2:
				if (dupindexL > 0 and dupindexR < n - 1) and string[dupindexL - 1] == string[dupindexR + 1]:
					goodsubs += 1 + nC2(dupcountr)
				else:
					goodsubs += nC2(dupcountr)
			tmpvar = string[i]
			dupcountr = 1
			dupindexL = dupindexR = i
		if i < n - 2 and (string[i] == string[i + 2] and string[i] != string[i + 1]):
			goodsubs += 1
	dupindexR = n - 1
	if dupcountr >= 2:
		goodsubs += nC2(dupcountr)
	print(goodsubs)


def sol(a, i, j):
	mid = int((i + j) / 2)
	if j - i == 0:
		return 0
	elif j - i == 1:
		if a[i] == a[j]:
			return 1
		else:
			return 0
	else:
		ans = 0
		pr = 1
		pl = 1
		ar = a[mid]
		al = a[mid + 1]
		lx = mid
		ly = mid + 1
		for x in range(mid - 1, i - 1, -1):
			if a[x] == ar:
				pr += 1
				lx = x
			else:
				break
		for x in range(mid + 2, j + 1):
			if a[x] == al:
				pl += 1
				ly = x
			else:
				break
		if ar == al:
			ans = pl * pr
			if lx != i and ly != j:
				if a[lx - 1] == a[ly + 1]:
					ans += 1
		else:
			if lx != i:
				if a[lx - 1] == al:
					ans += 1
			if ly != j:
				if a[ly + 1] == ar:
					ans += 1
		return ans + sol(a, i, mid) + sol(a, mid + 1, j)
t = int(input())
for r in range(t):
	a = input()
	n = len(a)
	ans = sol(a, 0, n - 1)
	print(ans)


for i in range(int(input())):
	s = str(input())
	ip = [[] for j in range(26)]
	count = 0
	for j in range(len(s)):
		ip[ord(s[j]) - 97].append(j)
	for j in ip:
		if len(j) < 2:
			continue
		else:
			for k in range(len(j) - 1):
				a = j[k]
				b = j[k + 1]
				if b == a + 1:
					pass
				else:
					br = 0
					m = s[a + 1]
					for l in range(a + 1, b):
						if s[l] != m:
							br = 1
							break
					if br == 0:
						count += 1
	count2 = 0
	for j in range(len(s) - 1):
		if s[j] == s[j + 1]:
			count2 += 1
		else:
			n = count2 + 1
			count += n * (n - 1) // 2
			count2 = 0
	n = count2 + 1
	count += n * (n - 1) // 2
	count2 = 0
	print(count)


for _ in range(int(input())):
	a = input().strip()
	ans = 0
	block = [[a[0], 1]]
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			block[-1][-1] += 1
			ans += 1
		else:
			block.append([a[i], 1])
	k = len(block)
	for i in range(k):
		if block[i][-1] > 2:
			n = block[i][-1]
			ans += (n - 2) * (n - 1) // 2
		if i <= k - 3 and block[i][0] == block[i + 2][0]:
			ans += 1
	print(ans)


for jjjj in range(int(input())):
	s = input()
	cnt = 0
	l = len(s)
	for i in range(0, l - 1):
		if s[i] == s[i + 1]:
			cnt += 1
	i = 0
	while i < l - 2:
		c = s[i]
		d = s[i + 1]
		e = s[i + 2]
		if c == d and e != c:
			i += 1
		elif c == d and e == c:
			k = 0
			for j in range(i + 3, l):
				if s[j] == c:
					k += 1
				else:
					break
			tot = 3 + k - 2
			cnt = cnt + tot * (tot + 1) // 2
			i = i + 2 + k - 1
		elif c != d and c == e:
			cnt += 1
			i += 1
		elif c != d and d == e:
			k = 0
			ans = 0
			for j in range(i + 3, l):
				if s[j] == e:
					k += 1
				elif s[j] == c:
					ans = 1
					break
				else:
					break
			if ans == 1:
				tot = k
				cnt = cnt + k * (k + 1) // 2
				i = i + 2 + k
				cnt += 1
			else:
				cnt = cnt + k * (k + 1) // 2
				i = i + 2 + k
		elif c != d and d != e:
			i = i + 1
	print(cnt)


t = int(input())
for test in range(t):
	s = input()
	if len(s) == 1:
		print(0)
		continue
	if len(s) == 2 and s[0] == s[1]:
		print(1)
		continue
	count = 0
	first = s[0]
	current = s[1]
	start = 0
	for i in range(2, len(s)):
		c = s[i]
		if c == first and current == first:
			continue
		if c == current:
			continue
		if c == first and current != first:
			l = i - start - 1
			count += l * (l - 1) // 2
			count += 1
			start = i - 1
			first = current
			current = c
			continue
		if c != first and current == first:
			l = i - start
			count += l * (l - 1) // 2
			current = c
			start = i - 1
			continue
		if c != first and current != first:
			l = i - start - 1
			count += l * (l - 1) // 2
			first = current
			current = c
			start = i - 1
			continue
	if first != current:
		l = len(s) - 1 - start
	else:
		l = len(s) - start
	count += l * (l - 1) // 2
	print(count)


T = int(input())
for _ in range(T):
	s = input()
	goodStrings = 0
	lastChainLetter = None
	(currentChainLetter, currentChainLength) = (s[0], 1)
	for i in range(1, len(s)):
		if s[i] == currentChainLetter:
			currentChainLength += 1
			continue
		else:
			goodStrings += int(0.5 * (currentChainLength - 1) * (currentChainLength - 1 + 1))
			if s[i] == lastChainLetter:
				goodStrings += 1
			(lastChainLetter, currentChainLetter) = (currentChainLetter, s[i])
			currentChainLength = 1
	goodStrings += int(0.5 * (currentChainLength - 1) * (currentChainLength - 1 + 1))
	print(goodStrings)


def count_substrings(s):
	n = len(s)
	sub = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			sub += 1
	for i in range(n - 2):
		l = s[i]
		chars = set([])
		for j in range(i + 1, n):
			if s[j] == l and len(chars) == 1:
				sub += 1
			chars.add(s[j])
			if len(chars) > 1:
				break
	return sub

def count_substrings_linear(s):
	n = len(s)
	sub = 0
	(alpha, c) = (s[0], 1)
	reduced_s = [alpha]
	for i in range(1, n):
		if s[i] == alpha:
			c += 1
		else:
			sub += c * (c - 1) // 2
			c = 1
			alpha = s[i]
			reduced_s.append(alpha)
	sub += c * (c - 1) // 2
	for i in range(1, len(reduced_s) - 1):
		if reduced_s[i - 1] == reduced_s[i + 1]:
			sub += 1
	return sub
t = int(input())
while t:
	s = input()
	sub = count_substrings_linear(s)
	print(sub)
	t -= 1


for _ in range(int(input().strip())):
	s = input().strip()
	s += '*'
	cnt = 1
	ans = 0
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			cnt += 1
		else:
			ans += cnt * (cnt - 1) // 2
			if i != cnt and s[i - cnt - 1] == s[i]:
				ans += 1
			cnt = 1
	print(ans)


def func(A):
	temp = A[0]
	cnt = 1
	ans = 0
	prev = ''
	for i in range(1, len(A)):
		if temp == A[i]:
			cnt += 1
		else:
			if prev != '':
				if A[i] == prev:
					ans += 1
			prev = temp
			temp = A[i]
			ans += int(cnt * (cnt - 1) / 2)
			cnt = 1
	ans += int(cnt * (cnt - 1) / 2)
	print(ans)

def main():
	t = int(input())
	for i in range(t):
		A = input()
		func(A)
main()


import math
t = int(input())
for i in range(t):
	n = input()
	count = 0
	if len(n) <= 1:
		print(0)
		continue
	else:
		i = 0
		j = 1
		flag = 0
		if n[i] == n[j]:
			count += 1
		i += 1
		j += 1
		while j < len(n):
			if n[i - 1] == n[j] and n[i] != n[j]:
				count += 1
				i += 1
				j += 1
			elif n[i] == n[j]:
				count += 1
				if i != 0:
					if flag == 0:
						k = i - 1
						flag = 1
				i += 1
				j += 1
			else:
				if flag == 1:
					if n[k] == n[j]:
						count += 1
					flag = 0
				i += 1
				j += 1
		j = 1
		count1 = 1
		while j < len(n):
			if n[j] == n[j - 1]:
				count1 += 1
			else:
				if count1 > 2:
					x = math.factorial(count1) / (math.factorial(count1 - 2) * math.factorial(2))
					count += int(x) - count1 + 1
				count1 = 1
			j += 1
		if count1 > 2:
			x = math.factorial(count1) / (math.factorial(count1 - 2) * math.factorial(2))
			count += int(x) - count1 + 1
	print(count)


def func():
	a = input()
	sum_ = 0
	prev = a[0]
	n = 1
	start = 0
	end = 0
	for i in a[1:]:
		if i == prev:
			n += 1
		else:
			sum_ += n * (n - 1) // 2
			if a[start] == i:
				sum_ += 1
			start = end
			prev = i
			n = 1
		end += 1
	sum_ += n * (n - 1) // 2
	print(sum_)
t = int(input())
for i in range(t):
	func()


t = int(input())
ctr = 0
while t > ctr:
	x = input()
	s = ''
	for i in range(len(x) - 1):
		if x[i] != x[i + 1]:
			s += x[i:i + 1] + ' '
		else:
			s += x[i:i + 1]
	if len(x) > 1 and x[-1] != x[-2]:
		s = s + ' ' + x[-1:]
	else:
		s += x[-1:]
	s = s.split()
	ans = 0
	for i in range(len(s)):
		if 1 <= i <= len(s) - 2:
			if s[i - 1][0] == s[i + 1][0]:
				ans += 1
		if len(s[i]) > 1:
			x = len(s[i])
			ans += x * (x - 1) / 2
	print(int(ans))
	ctr += 1


def fun(n):
	return int(n * (n + 1) / 2)
t = int(input())
while t > 0:
	s = input()
	ns = s[0]
	n = len(s)
	count = 0
	inc = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			inc = inc + 1
		else:
			count = count + fun(inc)
			ns = ns + s[i]
			inc = 0
	count = count + fun(inc)
	for i in range(2, len(ns)):
		if ns[i] == ns[i - 2]:
			count = count + 1
	print(count)
	t = t - 1


T = int(input())
for _ in range(T):
	S = input()
	GoodStrings = 0
	(CurrentChainLetter, CurrentChainLength) = (S[0], 1)
	LastChainLetter = None
	for i in range(1, len(S)):
		if S[i] == CurrentChainLetter:
			CurrentChainLength += 1
		else:
			GoodStrings += int(0.5 * CurrentChainLength * (CurrentChainLength - 1))
			if S[i] == LastChainLetter:
				GoodStrings += 1
			(LastChainLetter, CurrentChainLetter) = (CurrentChainLetter, S[i])
			CurrentChainLength = 1
	GoodStrings += int(0.5 * CurrentChainLength * (CurrentChainLength - 1))
	print(GoodStrings)


for _ in range(int(input())):
	s = input()
	d = ''
	c = s[0]
	cc = 0
	count = 0
	for i in range(len(s) + 1):
		if i < len(s) and s[i] == c:
			cc += 1
		elif i < len(s) and s[i] != c:
			d += c
			c = s[i]
			count += cc * (cc - 1) // 2
			cc = 1
		elif i == len(s):
			d += c
			count += cc * (cc - 1) // 2
	for i in range(len(d) - 2):
		if d[i] == d[i + 2]:
			count += 1
	print(count)


import functools
import operator as op

def ncr(n, r):
	if n < r:
		return 0
	r = min(r, n - r)
	if r == 0:
		return 1
	numer = functools.reduce(op.mul, range(n, n - r, -1))
	denom = functools.reduce(op.mul, range(1, r + 1))
	return numer // denom
t = int(input())
for test in range(t):
	array = input()
	ans = 0
	check = [array[0]]
	freq = [1]
	cur = array[0]
	flip = 0
	for i in array[1:]:
		if i != cur:
			cur = i
			flip += 1
		if flip == 2:
			if not i in check:
				ans += ncr(freq[0], 2)
				check = [check[1], i]
				freq = [freq[1], 1]
				cur = i
				flip = 1
			else:
				freq[check.index(i)] += 1
				ans += 1 + ncr(freq[0] - 1, 2)
				check = [check[1], i]
				freq = [freq[1], 1]
				cur = i
				flip = 1
		elif not i in check:
			check.append(i)
			freq.append(1)
		else:
			freq[check.index(i)] += 1
	if flip != 2:
		if len(check) == 2:
			ans += ncr(freq[0], 2) + ncr(freq[1], 2)
		elif len(check) == 1:
			ans += ncr(freq[0], 2)
	print(ans)


t = int(input())
for z in range(t):
	a = list(input())
	count = 0
	s = 0
	p = []
	a.append('$')
	for i in range(len(a) - 1):
		if a[i] == a[i + 1] and s != 1:
			p.append(i)
			c = 1
			s = 1
		elif a[i] != a[i + 1] and s == 1:
			p.append(i)
			s = 0
	for i in range(0, len(p), 2):
		k = p[i + 1] - p[i] + 1
		count += k * (k - 1) // 2
		if p[i + 1] + 1 <= len(a) and p[i] - 1 >= 0 and (a[p[i + 1] + 1] == a[p[i] - 1]):
			count += 1
	for i in range(len(a) - 2):
		if a[i] == a[i + 2] and a[i] != a[i + 1]:
			count += 1
	print(count)