Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Two strings $A$ and $B$ are *equivalent* (denoted by $A \sim B$) if they have the same lengths and $A$ can be transformed into $B$ by performing the following operation zero or more times: choose a substring of $A$ which contains '1' an even number of times and reverse this substring.

You are given a binary string $S$. Find the number of different equivalence classes of the substrings of this string. In other words, find the smallest possible size of a set $\mathcal{C}$ of binary strings with the following property: for each non-empty string $R$ which is a substring of $S$ (including $S$ itself), there is a string $X \in \mathcal{C}$ such that $R \sim X$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single string $S$ with length $N$.

------  Output ------
For each test case, print a single line containing one integer ― the number of equivalence classes among the substrings of the given string.

------  Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 1,000$
$S$ contains only characters '0' and '1'

------  Subtasks ------
Subtask #1 (10 points): $N ≤ 10$

Subtask #2 (90 points): original constraints

----- Sample Input 1 ------ 
10

00000

10001

10101

01111

11001

01101

10110

10010

10111

11001
----- Sample Output 1 ------ 
5

11

8

9

12

10

10

11

11

12

Difficulty: HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	st = input()
	s = set()
	for i in range(len(st)):
		ct = 0
		even = 0
		odd = 0
		for j in range(i, len(st)):
			if st[j] == '1':
				ct += 1
			elif ct % 2 == 0:
				even += 1
			else:
				odd += 1
			s.add((j - i + 1, even, odd))
	print(len(s))
	s.clear()


for _ in range(int(input())):
	S = input()
	N = len(S)
	substring = set()
	for i in range(N):
		cnt = 0
		odd = 0
		even = 0
		for j in range(i, N):
			if S[j] == '1':
				cnt += 1
			elif cnt % 2:
				odd += 1
			else:
				even += 1
			substring.add((j - i + 1, odd, even))
	print(len(substring))


for _ in range(int(input())):
	s = input()
	ans = set()
	for i in range(len(s)):
		ones = 0
		count = 0
		for j in range(i, len(s)):
			if s[j] == '1':
				ones += 1
			if ones & 1:
				count += 1
			ans.add((j - i + 1, ones, count))
	print(len(ans))


for _ in range(int(input())):
	st = input()
	s = set()
	for i in range(len(st)):
		ct = 0
		e = 0
		o = 0
		for j in range(i, len(st)):
			if st[j] == '1':
				ct += 1
			elif ct % 2 == 0:
				e += 1
			else:
				o += 1
			s.add((j - i + 1, e, o))
	print(len(s))
	s.clear()


for _ in range(int(input())):
	s = input()
	n = len(s)
	ms = set()
	for i in range(n):
		flag = 0
		ocnt = 0
		ecnt = 0
		c = 0
		for j in range(i, n):
			if s[j] == '1':
				c = c + 1
				flag = 1 - flag
			elif flag == 1:
				ocnt = ocnt + 1
			else:
				ecnt = ecnt + 1
			ms.add((c, (ocnt, ecnt)))
	print(len(ms))


for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = set()
	for i in range(n):
		cnt = 0
		even = 0
		odd = 0
		for j in range(i, n):
			if s[j] == '1':
				cnt += 1
			elif cnt % 2 == 0:
				even += 1
			else:
				odd += 1
			len_j = j - i + 1
			ans.add((len_j, even, odd))
	print(len(ans))


t = int(input())
for tc in range(t):
	s = input()
	n = len(s)
	ms = set()
	for i in range(n):
		flag = 0
		ocnt = 0
		ecnt = 0
		cnt = 0
		for j in range(i, n):
			if s[j] == '1':
				cnt = cnt + 1
				flag = 1 - flag
			elif flag == 1:
				ocnt = ocnt + 1
			else:
				ecnt = ecnt + 1
			ms.add((cnt, (ocnt, ecnt)))
	print(len(ms))


import sys
input = sys.stdin.readline
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip('\r\n')
for _ in range(ri()):
	s = rs()
	n = len(s)
	classes = set()
	for i in range(n):
		(o, z) = (0, 0)
		ct = 0
		for j in range(i, n):
			if s[j] == '1':
				o += 1
			else:
				z += 1
			if o % 2:
				ct += 1
			classes.add((o, z, ct))
	print(len(classes))


import sys

def mati(n):
	return [intl() for i in range(n)]
iinp = lambda : int(sys.stdin.readline())
inp = lambda : sys.stdin.readline().strip()
strl = lambda : list(inp().strip().split(' '))
intl = lambda : list(map(int, inp().split(' ')))
mint = lambda : map(int, inp().split())
flol = lambda : list(map(float, inp().split(' ')))
flush = lambda : sys.stdout.flush()

def sll(s, size, non, n01, l, so1, se, n):
	sew = set()
	sew.add(((non, n01), (so1, se)))
	for i in range(size, n):
		if s[i - size] == '1':
			l.pop(0)
			(se, so1) = (so1, se)
			non -= 1
		else:
			n01 -= 1
			l[0] -= 1
			se -= 1
		if s[i] == '1':
			non += 1
			l.append(0)
		else:
			n01 += 1
			l[-1] += 1
			if len(l) & 1:
				se += 1
			else:
				so1 += 1
		sew.add(((non, n01), (so1, se)))
	return len(sew)

def substr(s, n, le):
	l = []
	tm = non = n01 = so1 = se = cur = 0
	for i in range(n):
		if s[i] == '0':
			if not cur & 1:
				se += 1
			else:
				so1 += 1
			tm += 1
			n01 += 1
		else:
			l.append(tm)
			tm = 0
			cur += 1
			non += 1
	l.append(tm)
	return sll(s, n, non, n01, l, so1, se, le)
for _ in range(iinp()):
	s = inp()
	n = len(s)
	ans = 0
	for i in range(n):
		ans += substr(s, i + 1, n)
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	eqset = set()
	for i in range(0, n):
		(cnt, even, odd) = (0, 0, 0)
		for j in range(i, n):
			if s[j] == '1':
				cnt += 1
			elif cnt % 2:
				odd += 1
			else:
				even += 1
			l = j - i + 1
			eqset.add((l, even, odd))
	print(len(eqset))


from sys import stdin, stdout
import math
from itertools import permutations, combinations
from collections import defaultdict
from collections import Counter
from bisect import bisect_left
import sys
from queue import PriorityQueue
import operator as op
from functools import reduce
import re
mod = 1000000007
iinp = lambda : int(sys.stdin.readline())
inp = lambda : sys.stdin.readline().strip()
strl = lambda : list(inp().strip().split(' '))
intl = lambda : list(map(int, inp().split(' ')))
mint = lambda : map(int, inp().split())
flol = lambda : list(map(float, inp().split(' ')))
flush = lambda : sys.stdout.flush()

def myCode():
	s = inp()
	st = set()
	for i in range(len(s)):
		cnt = 0
		even = 0
		odd = 0
		for j in range(i, len(s)):
			if s[j] == '1':
				cnt += 1
			elif cnt % 2:
				odd += 1
			else:
				even += 1
			length = j - i + 1
			st.add(tuple((length, odd, even)))
	print(len(st))

def main():
	for t in range(iinp()):
		myCode()
main()


t = int(input())
for _ in range(t):
	s = input()
	temp = set()
	for i in range(len(s)):
		(cnt, even, odd) = (0, 0, 0)
		for j in range(i, len(s)):
			if s[j] == '1':
				cnt += 1
			elif cnt % 2 == 0:
				even += 1
			else:
				odd += 1
			temp.add(tuple([j - i + 1, even, odd]))
	print(len(temp))


try:
	t = int(input())
	for _ in range(t):
		s = input()
		li = list(s)
		ans = set()
		for i in range(len(s)):
			even = 0
			odd = 0
			count = 0
			for j in range(i, len(s)):
				if li[j] == '1':
					count += 1
				elif count % 2:
					odd += 1
				else:
					even += 1
				len1 = j - i + 1
				anst = str(len1) + ' ' + str(even) + ' ' + str(odd)
				ans.add(anst)
		print(len(ans))
except:
	pass


try:
	T = int(input())
	for i in range(T):
		s = input()
		n = len(s)
		C = set()
		for i in range(n):
			even = 0
			odd = 0
			count = 0
			for j in range(i, n):
				if s[j] == '1':
					count = count + 1
				elif count % 2 == 0:
					odd = odd + 1
				else:
					even = even + 1
				leng = j - i + 1
				tup = (leng, even, odd)
				C.add(tup)
		print(len(C))
except:
	pass


for _ in range(int(input())):
	s = input()
	ss = set()
	for i in range(len(s)):
		even = 0
		odd = 0
		cnt = 0
		for j in range(i, len(s)):
			if s[j] == '1':
				cnt += 1
			elif cnt % 2 == 0:
				odd += 1
			else:
				even += 1
			a = (cnt, odd, even)
			ss.add(a)
	print(len(ss))


for _ in range(int(input())):
	s = input()
	sd = set()
	for i in range(len(s)):
		count1 = 0
		count2 = 0
		count3 = 0
		for j in range(i, len(s)):
			if s[j] == '1':
				count1 += 1
			elif count1 & 1:
				count2 += 1
			else:
				count3 += 1
			sd.add(tuple([count3, count2, count1]))
	print(len(sd))


n = int(input())
for a in range(n):
	s = input()
	length = len(s)
	classes = {}
	for i in range(length):
		fi = ''
		sec = ''
		thi = ''
		fou = ''
		e = ''
		f = ''
		k = 0
		l = 0
		c = 0
		for j in range(i, length):
			ch = s[j]
			if ch == '0':
				if k == l:
					fi += '0'
				else:
					thi += '0'
			else:
				c += 1
				if c % 2 != 0:
					if c == 1:
						sec += '1'
					else:
						fou += '1'
					k += 1
				else:
					l += 1
					fou += '1'
			f = fi + sec + thi + fou
			classes[f] = 1
	print(len(classes))


for t in range(int(input())):
	s = input()
	n = len(s)
	ar = set()
	for i in range(n):
		cnt = 0
		ev = 0
		od = 0
		for j in range(i, n):
			if s[j] == '1':
				cnt = cnt + 1
			elif cnt % 2 == 0:
				ev = ev + 1
			else:
				od = od + 1
			l = j - i + 1
			ar.add((l, od, ev))
	print(len(ar))
	del ar
	del s


import sys
for _ in range(int(input())):
	str = input()
	count = 0
	x = set()
	length = len(str)

	def find(str):
		one = -1
		zero = -1
		for i in range(len(str) - 1, -1, -1):
			if str[i] == '1':
				one = i
				for j in range(one - 1, -1, -1):
					if str[j] == '1':
						zero = j + 1
						break
				break
		return (zero, one)
	for i in range(length):
		found1 = 0
		ind1 = 0
		found0 = 0
		ind0 = 0
		j = i + 1
		new_str = str[i]
		x.add(new_str)
		if new_str[0] == '1':
			found1 += 1
		for j in range(i + 1, length):
			if str[j] == '1':
				found1 += 1
				if found1 > 1:
					str1 = new_str[:ind0]
					str2 = new_str[ind0:]
					str2 += '1'
					str2 = str2[::-1]
					new_str = str1 + str2
					x.add(new_str)
					ind0 += 1
				else:
					new_str += '1'
					x.add(new_str)
			elif str[j] == '0':
				new_str += '0'
				x.add(new_str)
	print(len(x))


try:
	t = int(input())
	for _ in range(t):
		s = input()
		my_set = set()
		for i in range(len(s)):
			cnt = 0
			even = 0
			odd = 0
			for j in range(i, len(s)):
				if s[j] == '1':
					cnt += 1
				elif cnt % 2 == 0:
					even += 1
				else:
					odd += 1
				length = j - i + 1
				my_set.add((length, even, odd))
		print(len(my_set))
except:
	pass


import sys
import math
import bisect
from math import floor, sqrt, log
from collections import defaultdict
scanf = lambda n: [int(i) for i in sys.stdin.readline().split()][:n]
cin = lambda : map(int, sys.stdin.readline().split())
rint = lambda : int(sys.stdin.readline())
rstring = lambda : input()
cout = lambda tt, x: sys.stdout.write('Case #' + str(tt) + ': ' + str(x) + '\n')
abserror = lambda ans, upto: '{:.{}f}'.format(ans, upto)
sys.setrecursionlimit(100000)
mod = 1000000007

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

def mod_inverse(a, n):
	N = n
	xx = 0
	yy = 1
	y = 0
	x = 1
	while n > 0:
		q = a // n
		t = n
		n = a % n
		a = t
		t = xx
		xx = x - q * xx
		x = t
		t = yy
		yy = y - q * yy
		y = t
	x %= N
	x += N
	x %= N
	return x

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 * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime

def solve():
	string = rstring()
	n = len(string)
	ans = set()
	for i in range(n):
		(lenght, even, odd) = (0, 0, 0)
		ones = 0
		for j in range(i, n):
			lenght += 1
			if string[j] == '1':
				ones += 1
			elif ones % 2 == 0:
				even += 1
			else:
				odd += 1
			ans.add((lenght, odd, even))
	print(len(ans))
ttestcases = rint()
for testcase in range(1, ttestcases + 1):
	solve()


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	mlist = []
	for j in range(n):
		(cnt, even, odd) = (0, 0, 0)
		for k in range(j, n):
			length = k - j + 1
			if s[k] == '1':
				cnt += 1
			elif cnt % 2 == 0:
				even += 1
			else:
				odd += 1
			mlist.append((length, even, odd))
	print(len(set(mlist)))


for _ in range(int(input())):
	s = input()
	n = len(s)
	k = set()
	for i in range(n):
		c = 0
		even = 0
		odd = 0
		for j in range(i, n):
			if s[j] == '1':
				c += 1
			elif c % 2 == 0:
				odd += 1
			else:
				even += 1
			h = j - i + 1
			k.add((h, even, odd))
	print(len(k))


T = int(input())
for _ in range(T):
	s = input()
	n = len(s)
	ans_set = set()
	for i in range(n):
		(cnt, ev, od) = (0, 0, 0)
		for j in range(i, n):
			if s[j] == '1':
				cnt += 1
			else:
				if cnt % 2:
					od += 1
				if cnt % 2 == 0:
					ev += 1
			ans_set.add(tuple([j - i + 1, ev, od]))
	print(len(ans_set))


for testCase in range(int(input())):
	string = input()
	n = len(string)
	triplets = []
	for i in range(n):
		(count0, sum0alt, oddpos) = (0, 0, True)
		for j in range(i, n):
			if string[j] == '0':
				count0 += 1
				if oddpos:
					sum0alt += 1
			else:
				oddpos = not oddpos
			triplets.append((sum0alt, count0, j - i + 1 - count0))
	print(len(set(triplets)))


def solve(s):
	st = set()
	for i in range(len(s)):
		(count, even, odd) = (0, 0, 0)
		for j in range(i, len(s)):
			if s[j] == '1':
				count += 1
			elif count % 2:
				odd += 1
			else:
				even += 1
			ln = j - i + 1
			st.add((ln, even, odd))
	return len(st)
for t in range(int(input())):
	s = input()
	print(solve(s))


from collections import defaultdict
for _ in range(int(input())):
	s = input()
	n = len(s)
	if s[0] == '0':
		countofone = [0]
	else:
		countofone = [1]
	for i in range(1, len(s)):
		if s[i] == '0':
			countofone.append(countofone[i - 1])
		else:
			countofone.append(countofone[i - 1] + 1)
	ans = 1
	if countofone[-1] == n:
		ans += 1
	elif countofone[-1] == 0:
		ans += 1
	else:
		ans += 2
	maps = {}
	for i in range(n):
		maps[i + 1] = defaultdict(list)
	table = [[0 for i in range(n)] for j in range(n)]
	noofones = 0
	for i in range(n):
		noofones = 0
		for j in range(i + 1, n):
			if s[j] == '0':
				if i == 0:
					noofones = countofone[j]
				else:
					noofones = countofone[j] - countofone[i - 1]
				if noofones % 2 == 1:
					table[i][j] = table[i][j - 1] + 1
				else:
					table[i][j] += table[i][j - 1]
			else:
				table[i][j] += table[i][j - 1]
	start = 0
	end = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			start = i
			end = j
			length = end - start + 1
			if i == 0:
				one = countofone[j]
			else:
				one = countofone[j] - countofone[i - 1]
			tmp = table[i][j]
			maps[length][one].append(tmp)
	for i in range(n - 1):
		for j in maps[i + 1]:
			maps[i + 1][j] = list(set(maps[i + 1][j]))
			ans += len(maps[i + 1][j])
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	d = set()
	for i in range(n):
		(count, even, odd) = (0, 0, 0)
		for j in range(i, n):
			if s[j] == '1':
				count += 1
			elif count % 2 == 1:
				odd += 1
			else:
				even += 1
			l = j - i + 1
			d.add((l, even, odd))
	print(len(d))


for _ in range(int(input())):
	s = input()
	l = []
	ans = 0
	n = len(s)
	eq = set()
	for i in range(n):
		c = 0
		e = 0
		o = 0
		for j in range(i, n):
			if s[j] == '1':
				c += 1
			elif c % 2 == 0:
				e += 1
			else:
				o += 1
			ls = j - i + 1
			eq.add((ls, (e, o)))
	print(len(eq))


import sys

def solve(bits):
	soln = 0
	bids = set()
	for i in range(0, len(bits)):
		left_ones = 0
		even_zeros = 0
		odd_zeros = 0
		for j in range(i, len(bits)):
			b = bits[j]
			if b == 1:
				left_ones += 1
			elif b == 0:
				if left_ones % 2:
					odd_zeros += 1
				else:
					even_zeros += 1
			length = i - j + 1
			bids.add((length, even_zeros, odd_zeros))
	return len(bids)

def main():
	test_cases = int(sys.stdin.readline())
	for _ in range(test_cases):
		bits = tuple((int(i) for i in sys.stdin.readline().strip()))
		print(solve(bits))
main()


t = int(input())
for _ in range(t):
	a = list(input())
	s = set()
	l = len(a)
	ss = []
	for i in range(l):
		ss.append([])
		k = (1, int(a[i]), int(a[i]))
		ss[0].append(k)
		s.add(k)
	for i in range(2, l + 1):
		for j in range(l - i + 1):
			a1 = i
			b = ss[i - 2][j][1] + int(a[j + i - 1])
			c = ss[i - 2][j][2]
			c += b % 2
			s.add((a1, b, c))
			ss[i - 1].append((a1, b, c))
	print(len(s))


import sys, collections, math, itertools, random
INF = sys.maxsize

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

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

def input():
	return sys.stdin.readline().strip()
mod = 1000000007

def slide(s, size, no, nz, l, so, se, n):
	sew = set()
	arr = []
	sew.add(((no, nz), (so, se)))
	for i in range(size, n):
		if s[i - size] == '1':
			del l[0]
			t = se
			se = so
			so = t
			no -= 1
		else:
			nz -= 1
			l[0] -= 1
			se -= 1
		if s[i] == '1':
			no += 1
			l.append(0)
		else:
			nz += 1
			l[-1] += 1
			if len(l) % 2 == 1:
				se += 1
			else:
				so += 1
		sew.add(((no, nz), (so, se)))
	return len(sew)

def subsstring(s, n, len):
	l = []
	rt = 0
	no = 0
	nz = 0
	so = 0
	se = 0
	cur = 0
	for i in range(n):
		if s[i] == '0':
			if cur % 2 == 0:
				se += 1
			else:
				so += 1
			rt += 1
			nz += 1
		else:
			l.append(rt)
			rt = 0
			cur += 1
			no += 1
	l.append(rt)
	return slide(s, n, no, nz, l, so, se, len)
for _ in range(int(input())):
	s = input()
	ans = 0
	for i in range(len(s)):
		ans += subsstring(s, i + 1, len(s))
	print(ans)


for _ in range(int(input())):
	s = input()
	parametre = set()
	for i in range(len(s)):
		(length, even, odd) = (0, 0, 0)
		for j in range(i, len(s)):
			if s[j] == '1':
				length += 1
			elif length % 2 == 0:
				even += 1
			else:
				odd += 1
			parametre.add((j - i + 1, even, odd))
	print(len(parametre))


import math
t = int(input())
while t > 0:
	ans = list()
	t -= 1
	s = input().strip()
	n = len(s)
	for i in range(0, n):
		e = 0
		o = 0
		c = 0
		for j in range(i, n):
			if s[j] == '1':
				c += 1
			elif c & 1 == 0:
				e += 1
			else:
				o += 1
			t1 = (j - i + 1, o, e)
			ans.append(t1)
	print(len(set(ans)))


import sys
import math
from math import *
from collections import Counter, defaultdict, deque
from bisect import bisect_left
import random
lip = lambda : list(map(int, input().split()))
ip = lambda : int(input())
sip = lambda : input().split()
mod = 10 ** 9 + 7

def main():
	s = input()
	dp = set()
	n = len(s)
	ans = 0
	for i in range(n):
		cnt = 0
		odd = 0
		even = 0
		for j in range(i, n):
			if s[j] == '1':
				cnt += 1
			elif cnt & 1:
				odd += 1
			else:
				even += 1
			t = (j - i + 1, even, odd)
			if t not in dp:
				ans += 1
				dp.add(t)
	print(ans)
for i in range(ip()):
	main()


test = int(input())
for sdfas in range(test):
	s = input()
	n = len(s)
	myset = set()
	for l in range(n):
		length = 0
		ones = 0
		odd = 0
		for r in range(l + 1, n + 1):
			length += 1
			if s[r - 1] == '1':
				ones += 1
			elif ones % 2:
				odd += 1
			myset.add((length, ones, odd))
	print(len(myset))


import itertools
import math
t = int(input())
for _ in range(t):
	s = input()
	distinct = set()
	for i in range(len(s)):
		cnt1 = 0
		evens = 0
		odds = 0
		for j in range(i, len(s)):
			if s[j] == '1':
				cnt1 += 1
			elif cnt1 % 2 == 1:
				odds += 1
			else:
				evens += 1
			distinct.add((j + 1 - i, evens, odds))
	print(len(distinct))


from itertools import combinations
t = int(input())
for _ in range(t):
	s = input()
	ans = []
	for i in range(len(s)):
		count = 0
		odd = 0
		even = 0
		for j in range(i, len(s)):
			if s[j] == '1':
				count += 1
			elif count % 2 == 1:
				odd += 1
			else:
				even += 1
			l = j - i + 1
			ans.append((l, even, odd))
	print(len(set(ans)))


t = int(input())
while t:
	t -= 1
	s = input()
	myset = set()
	n = len(s)
	for i in range(n):
		(count, even, odd) = (0, 0, 0)
		for j in range(i, n):
			if s[j] == '1':
				count += 1
			elif count & 1:
				odd += 1
			else:
				even += 1
			l = j - i + 1
			myset.add((l, odd, even))
	print(len(myset))


from collections import Counter
x = set()

def subString(s, n):
	for i in range(n):
		(n1, even, odd) = (0, 0, 0)
		for j in range(i, n):
			n1 += s[j] == '1'
			if n1 % 2 == 0:
				even += s[j] == '0'
			else:
				odd += s[j] == '0'
			x.add((n1, (odd, even)))
for _ in range(int(input())):
	n = input()
	subString(n, len(n))
	print(len(x))
	x.clear()


for t in range(int(input())):
	s = input()
	eq_class = set()
	for i in range(len(s)):
		(ct, ev, od) = (0, 0, 0)
		for j in range(i, len(s)):
			if s[j] == '1':
				ct += 1
			elif ct % 2:
				od += 1
			else:
				ev += 1
			length = j - i + 1
			eq_class.add((length, ev, od))
	print(len(eq_class))


for _ in range(int(input())):
	x = input()
	eq = set()
	for i in range(0, len(x)):
		c = e = o = 0
		j = i
		while j < len(x):
			ll = []
			if x[j] == '1':
				c += 1
			elif c % 2:
				o += 1
			else:
				e += 1
			j += 1
			ll.append(j - i + 1)
			ll.append(e)
			ll.append(o)
			eq.add(tuple(ll))
	print(len(eq))


def main():
	T = int(input())
	for _ in range(T):
		S = input()
		triplets = set()
		for i in range(len(S)):
			X = S[i]
			no_ones = 1 if S[i] == '1' else 0
			sumSub = int(S[i])
			countI = 0
			if sumSub % 2 == 1:
				countI = 1
			triplets.add((len(X), no_ones, countI))
			for j in range(i + 1, len(S)):
				X += S[j]
				if S[j] == '1':
					no_ones += 1
				sumSub += int(S[j])
				if sumSub % 2 == 1:
					countI += 1
				triplets.add((len(X), no_ones, countI))
		print(len(triplets))
main()


for _ in range(int(input())):
	sg = input().strip()
	l = len(sg)
	cnt = 0
	st = set()
	for i in range(l):
		evens = 0
		odds = 0
		ones = 0
		for j in range(i, l):
			if sg[j] == '1':
				ones += 1
			elif ones % 2 == 0:
				evens += 1
			else:
				odds += 1
			lth = j - i + 1
			st.add((lth, odds, evens))
	print(len(st))


def solve(s):
	classes = set()
	for i in range(len(s)):
		counts = {0: 0, 1: 0}
		phase = False
		for j in range(i, len(s)):
			if s[j] == '0':
				counts[phase] += 1
			elif s[j] == '1':
				phase = not phase
			classes.add((counts[0], counts[1], i - j))
	return len(classes)
for _ in range(int(input())):
	print(solve(input()))


from sys import stdin, stdout
for _ in range(int(input())):
	string = input()
	n = len(string)
	triplets = []
	for i in range(n):
		(count0, sum0alt, oddpos) = (0, 0, True)
		for j in range(i, n):
			if string[j] == '0':
				count0 += 1
				if oddpos:
					sum0alt += 1
			else:
				oddpos = not oddpos
			triplets.append((sum0alt, count0, j - i + 1 - count0))
	print(len(set(triplets)))


from sys import stdin
from collections import defaultdict as D

def func(Str, lenOfStr, d):
	(c, iz) = (0, -1)
	for i in range(lenOfStr):
		if Str[i] == '1':
			if iz != -1:
				c += 1
		elif iz == -1:
			iz = i
		if iz != -1 and c == 2:
			new = Str[iz:i + 1]
			new = new[::-1]
			Str = Str[:iz] + new + Str[i + 1:]
			iz = Str.index('0')
			c = Str[iz + 1:i + 1].count('1')
		d[Str[:i + 1]] = 1

def main():
	for _ in range(int(input())):
		s = input()
		n = len(s)
		d = D(lambda : 0)
		d[s[-1]] = 1
		temp = s[-1]
		for i in range(n - 2, -1, -1):
			temp = s[i] + temp
			func(temp, n - i, d)
		print(len(d))
main()


def findAns(st, n, length):

	def slide(st, size, d, c, lis, b, a, n):
		ste = set()
		ste.add(((d, c), (b, a)))
		for i in range(size, n):
			if st[i - size] == '1':
				lis.pop(0)
				t = a
				a = b
				b = t
				d -= 1
			else:
				c -= 1
				lis[0] -= 1
				a -= 1
			if st[i] == '1':
				d += 1
				lis.append(0)
			else:
				c += 1
				lis[len(lis) - 1] += 1
				if len(lis) % 2 == 1:
					a += 1
				else:
					b += 1
			ste.add(((d, c), (b, a)))
		return len(ste)
	a = 0
	b = 0
	rt = 0
	c = 0
	lis = []
	cur = 0
	d = 0
	for i in range(n):
		if st[i] == '0':
			if cur % 2 == 0:
				a += 1
			else:
				b += 1
			rt += 1
			c += 1
		else:
			lis.append(rt)
			rt = 0
			cur += 1
			d += 1
	lis.append(rt)
	return slide(st, n, d, c, lis, b, a, length)

def solve(st):
	ans = 0
	for i in range(len(st)):
		ans += findAns(st, i + 1, len(st))
	print(ans)
for t in range(int(input())):
	st = input()
	solve(st)


def check_krle(g=9):
	a = 5 * 6
	b = a / 5
	c = b - 9
	e = c * 12
	return 500 * e
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	acount = 0
	st = []
	for i in range(n):
		st.append(set())
	faltu = check_krle()
	for i in range(0, n):
		curr = ''
		(f, b) = (0, 0)
		for j in range(i, n):
			s_temp = curr + s[j]
			if s[j] == '0':
				b = 0
				curr = s_temp
				st[j - i].add(curr)
				continue
			if f == j - i:
				curr = s_temp
				f += 1
				b += 1
				st[j - i].add(curr)
				continue
			else:
				b += 1
				new_str = s_temp[f:j - i + 1]
				ones = new_str.count('1')
				if ones % 2 == 0:
					new_temp = s_temp[:f] + new_str[::-1]
					f += b
					b = 0
					s_temp = new_temp
			curr = s_temp
			st[j - i].add(curr)
	for i in st:
		acount += len(i)
	print(acount)


t = int(input())
for i in range(t):
	st = input()
	ln = len(st)
	subset = set()
	for i in range(1, ln + 1):
		z = 0
		o = 0
		to = 0
		(seven, sodd) = (0, 0)
		l = []
		ret = 0
		for j in range(i):
			if st[j] == '1':
				o += 1
				l.append(ret)
				ret = 0
			else:
				if o % 2 == 0:
					seven += 1
				else:
					sodd += 1
				z += 1
				ret += 1
		l.append(ret)
		subset.add(((z, o), (seven, sodd)))
		for j in range(i, ln):
			if st[j - i] == '1':
				l.pop(0)
				o -= 1
				(seven, sodd) = (sodd, seven)
			else:
				z -= 1
				l[0] = -1
				seven -= 1
			if st[j] == '1':
				o += 1
				l.append(0)
			else:
				l[-1] += 1
				if len(l) % 2 == 1:
					seven += 1
				else:
					sodd += 1
				z += 1
			subset.add(((z, o), (seven, sodd)))
	print(len(subset))


t = int(input())
while t:
	s = input()
	leng = len(s)
	set1 = {}
	for i in range(leng):
		a = ''
		b = ''
		c = ''
		d = ''
		e = ''
		f = ''
		k = 0
		l = 0
		count = 0
		for j in range(i, leng):
			ch = s[j]
			if ch == '0':
				if k == l:
					a += '0'
				else:
					c += '0'
			else:
				count += 1
				if count % 2 != 0:
					if count == 1:
						b += '1'
					else:
						d += '1'
					k += 1
				else:
					l += 1
					d += '1'
			f = a + b + c + d
			set1[f] = 1
	print(len(set1))
	t -= 1


def fun():
	stringu = input()
	setum = set()
	for i in range(len(stringu)):
		ap = ''
		imh = ''
		newz = ''
		lun = ''
		mn1 = 0
		mn2 = 0
		c = 0
		for j in range(i, len(stringu)):
			ch = stringu[j]
			bw = ''
			if ch == '0':
				if mn1 == mn2:
					ap += '0'
				else:
					newz = newz + '0'
			if ch == '1':
				c += 1
				if c % 2 != 0:
					if c == 1:
						imh += '1'
					else:
						lun += '1'
					mn1 += 1
				else:
					mn2 += 1
					lun += '1'
			answer = ap + imh + newz + lun
			setum.add(answer)
	return len(setum)
T = int(input())
while T > 0:
	print(fun())
	T -= 1


t = int(input())
for i in range(t):
	s = input()
	result = 0
	for k in range(0, len(s)):
		s1 = 0
		s2 = 0
		th1 = 0
		th = 0
		even = 0
		odd = 0
		list1 = []
		list1.clear()
		n = k + 1
		n1 = n
		for l in range(0, n1):
			if s[l] != '1':
				if th % 2 == 0:
					even = even + 1
					s1 = s1 + 1
					s2 = s2 + 1
				else:
					s1 = s1 + 1
					s2 = s2 + 1
					odd = odd + 1
			else:
				list1.append(s1)
				s1 = s2
				s1 = 0
				th = th + s1
				th1 = th1 + s1
				th = th + 1
				th1 = th1 + 1
		list1.append(s1)
		list2 = set()
		list2.add(((th1, s2), (odd, even)))
		size = k + 1
		n = len(s)
		for j in range(size, n):
			if s[j - size] == '0':
				s2 = s2 - 1
				list1[0] = list1[0] - 1
				even = even - 1
			else:
				x = even
				y = odd
				x = x ^ y
				y = x ^ y
				x = x ^ y
				odd = y
				even = x
				th1 = th1 - 1
				list1.pop(0)
			if s[j] != '0':
				th1 = th1 + 1
				list1.append(0)
			else:
				s2 = s2 + 1
				list1[len(list1) - 1] = list1[len(list1) - 1] + 1
				if len(list1) % 2 != 1:
					odd = odd + 1
				else:
					even = even + 1
			list2.add(((th1, s2), (odd, even)))
		result = result + len(list2)
	print(result)


try:
	from collections import defaultdict

	def leastindex(s, cache1, cache2):
		chk = True
		zero1 = 0
		zero2 = 0
		for i in range(len(s)):
			if chk and s[i] == '0':
				zero1 += 1
			elif chk:
				chk = False
			elif s[i] == '1':
				chk = True
			else:
				zero2 += 1
			cache1.append(zero1)
			cache2.append(zero2)
		return
	t = int(input())
	for _ in range(t):
		c = defaultdict(lambda : set())
		string = input()
		cache1 = []
		cache2 = []
		leastindex(string, cache1, cache2)
		for i in range(len(string)):
			if i > 0:
				if string[i - 1] == '0':
					for j in range(i, len(cache1)):
						cache1[j] -= 1
				else:
					temp = cache1
					cache1 = cache2
					cache2 = temp
			for j in range(i, len(cache1)):
				length = j + 1 - i
				ele1 = cache1[j]
				ele2 = cache2[j]
				c[length].add((ele1, ele2))
		ans = 0
		for i in c:
			ans += len(c[i])
		print(ans)
except EOFError:
	pass


for _ in range(int(input())):
	st = input().strip()
	ls = len(st)
	combs = set()
	for i in range(0, ls):
		idx = -1
		fst = -1
		for j in range(i, ls):
			if st[j] == '0':
				if idx == -1:
					idx = j
			elif idx != -1:
				if fst == -1:
					fst = j
				else:
					fst = idx + j - fst
					idx += 1
					if idx == fst:
						idx += 1
						fst = -1
			combs.add((j - i + 1, idx - i if idx >= i else -1, fst - i if fst >= i else -1))
	print(len(combs))


from collections import defaultdict as dd
for _ in range(int(input())):
	s = input()
	le = len(s)
	d = dd(int)
	ans = 0
	for i in range(0, le):
		prevone = 0
		x = 0
		for j in range(i, le):
			if s[j] == '0' and prevone % 2 == 0:
				x += 1
			if s[j] == '1':
				prevone += 1
			if d[prevone, x, j - i + 1] != 1:
				ans += 1
				d[prevone, x, j - i + 1] = 1
	print(ans)


def slide(string, size, no, nz, l, so, se, n):
	final_solve = set()
	final_solve.add(((no, nz), (so, se)))
	for i in range(size, n):
		if string[i - size] == '1':
			l = l[1:]
			(se, so) = (so, se)
			no -= 1
		else:
			nz -= 1
			l[0] -= 1
			se -= 1
		if string[i] == '1':
			no += 1
			l.append(0)
		else:
			nz += 1
			l[-1] += 1
			if len(l) % 2 == 1:
				se += 1
			else:
				so += 1
		final_solve.add(((no, nz), (so, se)))
	return len(final_solve)

def substring(s, n, full_len):
	l = list()
	(rt, no, nz, so, se, cur) = (0, 0, 0, 0, 0, 0)
	for i in range(n):
		if s[i] == '0':
			if cur % 2 == 0:
				se += 1
			else:
				so += 1
			rt += 1
			nz += 1
		else:
			l.append(rt)
			rt = 0
			cur += 1
			no += 1
	l.append(rt)
	return slide(s, n, no, nz, l, so, se, full_len)
for _ in range(int(input())):
	s = input()
	ans = 0
	n = len(s)
	for i in range(n):
		ans += substring(s, i + 1, n)
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	eqcl = set()
	for l in range(n):
		zeros = [0, 0]
		parity = 0
		for r in range(l, n):
			if s[r] == '0':
				zeros[parity] += 1
			else:
				parity = 1 - parity
			eqcl.add((zeros[0], zeros[1], r - l))
	print(len(eqcl))


import sys
from math import gcd, ceil, sqrt, ceil
from math import gcd, ceil, floor, sqrt, copysign, factorial, fmod, fsum, degrees
from math import expm1, exp, log, log2, acos, asin, cos, tan, sin, pi, e, tau, inf, nan, atan2
INF = float('inf')
MOD = 998244353
mod = 10 ** 9 + 7
from collections import Counter, defaultdict as df
from functools import reduce

def counter(l):
	return dict(Counter(l))

def printm(l):
	for i in range(len(l)):
		print(l[i])

def P(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, ceil(sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
import math

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

def so(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

def rev(l):
	return list(reversed(l))

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

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

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

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

def inputm(n, m):
	return [input() for i in range(n)]

def d(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def solve():
	Jaiparshuram = input()
	n = len(Jaiparshuram)
	s = set()
	count = 0
	c4 = 0
	for i in range(n):
		(c1, c2, c3) = (0, 0, 0)
		for j in range(i, n):
			if Jaiparshuram[j] == '1':
				c1 += 1
			if Jaiparshuram[j] == '0' and 1 ^ c1 & 1:
				c2 += 1
			elif Jaiparshuram[j] == '0' and c1 & 1:
				c3 += 1
			else:
				c4 += 1
			s.add((c1, c2, c3))
	count = len(s)
	print(count)
for i in range(ini()):
	solve()


t = int(input())
for test in range(t):
	s = input()
	n = len(s)
	ans = set()
	for i in range(n):
		count_1 = 0
		count_0 = 0
		for j in range(i, n):
			l = j - i + 1
			if s[j] == '1':
				count_1 += 1
			elif s[j] == '0' and count_1 % 2 != 0:
				count_0 = count_0 + 1
			ans.add((l, count_0, count_1))
	print(len(ans))


import sys
import math
from math import *
from collections import Counter, defaultdict, deque
from bisect import bisect_left
lip = lambda : list(map(int, input().split()))
ip = lambda : int(input())
sip = lambda : input().split()
mod = 10 ** 9 + 7

def main():
	s = input()
	n = len(s)
	dp = defaultdict(lambda : set())
	visitor = dict()
	pt = dict()
	ans = 0
	for i in range(n):
		t = ''
		prev = 0
		ctr = 0
		for j in range(i, n):
			if s[j] == '1':
				ctr += 1
			t += s[j]
			if t[prev] == '1':
				prev += 1
				ctr -= 1
				if ctr < 0:
					ctr = 0
			pt[t] = (ctr, prev)
			if t in dp[j - i + 1]:
				if t in visitor:
					t = visitor[t]
					(ctr, prev) = pt[t]
				continue
			elif ctr == 2:
				ctr = 1
				dp[j - i + 1].add(t)
				visitor[t] = t[:prev] + t[prev:][::-1]
				pt[t] = (ctr, prev)
				t = visitor[t]
				prev += 1
				pt[t] = (ctr, prev)
			if prev < len(t) and t[prev] == '1':
				prev += 1
				ctr -= 1
				if ctr < 0:
					ctr = 0
			if t not in dp[j - i + 1]:
				dp[j - i + 1].add(t)
				ans += 1
	print(ans)
for i in range(ip()):
	main()


import io, sys, atexit, os
import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations
from itertools import combinations

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

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

def nu():
	return int(input())

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

def lcm(x, y):
	gg = find_gcd(x, y)
	return x * y // gg
mm = 1000000007

def solve():
	t = nu()
	for tt in range(t):
		s = input()
		n = len(s)
		ss = set()
		for i in range(n):
			c1 = 0
			pe = 0
			for j in range(i, n):
				if s[j] == '1':
					c1 += 1
				if c1 % 2 == 0:
					pe += 1
				ss.add((j - i + 1, c1, pe))
		print(len(ss))
solve()


t = int(input())
while t > 0:
	s = input()
	n = len(s)
	answer = 0
	mset = set()
	for i in range(1, n + 1):
		no = 0
		sum1 = 0
		c = 0
		j = 1
		while i - j >= 0:
			vec = []
			k = i - j
			if s[k] == '1':
				no = no + 1
				c = c + 1
			if c % 2 != 0 and s[k] != '1':
				sum1 = sum1 + 1
			vec.append(no)
			vec.append(sum1)
			vec.append(j)
			o = tuple(vec)
			mset.add(o)
			j = j + 1
	t = t - 1
	print(len(mset))


def countfrontones(temp):
	return 5
	num = 0
	n = len(temp)
	while num < n and temp[num] == '1':
		num += 1
		continue
	return num
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	arr = []
	for i in range(n):
		arr.append(set())
	for i in range(n):
		prev = ''
		prevs = 0
		preve = 0
		for l in range(1, n - i + 1):
			temp = prev + s[i + l - 1]
			ans = temp
			if s[i + l - 1] == '0':
				preve = 0
				arr[l - 1].add(ans)
				prev = ans
				continue
			if l == 1 or prevs == l - 1:
				prevs += 1
			preve += 1
			num = prevs
			neww = temp[num:l]
			ones = neww.count('1')
			if ones % 2 == 0:
				neww = temp[:num] + neww[::-1]
				if preve > 0:
					if prevs == l:
						prevs = num
					else:
						prevs += preve
						preve = 0
					ans = neww
			arr[l - 1].add(ans)
			prev = ans
	ans = 0
	for i in arr:
		ans += len(i)
	print(ans)