You are given a binary string S.  
In one operation, you can pick an index i (1≤ i < |S|) and swap the characters S_{i} and S_{(i+1)}.

Find the minimum number of operations required, such that, the decimal representation of the final binary string is divisible by 3. If it is impossible to do so, print -1 instead.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of single line of input, containing a binary string S.

------ Output Format ------ 

For each test case, output on a new line, the minimum number of operations required, such that, the decimal representation of the final binary string is divisible by 3. If it is impossible to do so, print -1 instead.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ |S| ≤ 3\cdot 10^{5}$
$S$ consists of $0$ and $1$ only.
- The sum of $|S|$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
0000
111
11001
----- Sample Output 1 ------ 
0
-1
1
----- explanation 1 ------ 
Test case $1$: There is no need to apply any operation since the decimal representation of $0000$ is $0$ which is divisible by $3$.

Test case $2$: It can be shown that we cannot make the decimal representation of the string divisible by $3$ using any number of operations.

Test case $3$: The decimal representation of $11001$ is $25$ . Using one operation, we pick $i = 2$ and swap $S_{2}$ and $S_{3}$. Thus, the string becomes $10101$, whose decimal representation is $21$, which is divisible by $3$.

Difficulty: HARD
Tags: Dynamic programming

Constructive algorithms

Ad-hoc
Skill types: Dynamic programming

Starter code:

Solutions:
def issubsequence(s1, s2):
	(n, m) = (len(s1), len(s2))
	(i, j) = (0, 0)
	while i < n and j < m:
		if s1[i] == s2[j]:
			i += 1
		j += 1
	return i == n

def U(S):
	N = len(S)
	x = 0
	y = 0
	for j in range(1, N - 1, 2):
		if S[j] == '1' and S[j + 1] == '0':
			x += 1
	for j in range(1, N, 2):
		if S[j] == '1' and S[j - 1] == '0':
			x += 1
	for j in range(0, N - 1, 2):
		if S[j] == '1' and S[j + 1] == '0':
			y += 1
	for j in range(2, N, 2):
		if S[j] == '1' and S[j - 1] == '0':
			y += 1
	return (x, y)
a = int(input())
for i in range(a):
	S = input()
	x = int(S, 2)
	N = len(S)
	A = list(S)
	A.reverse()
	S = ''
	for j in range(N):
		S += A[j]
	ans = 0
	p = S.count('0')
	if N == 1:
		if S[0] == '0':
			ans = 0
		else:
			ans = -1
	elif N >= 4:
		if x % 3 == 0:
			ans = 0
		elif x % 3 == 1:
			if p == 0:
				ans = -1
			elif U(S)[0] >= 1:
				ans = 1
			elif issubsequence('1001', S) == True or issubsequence('0110', S) == True or issubsequence('1010', S) == True or (issubsequence('0101', S) == True):
				ans = 2
			elif p == 1 or p == N - 1:
				ans = -1
			else:
				ans = 3
		elif p == 0:
			ans = -1
		elif U(S)[1] >= 1:
			ans = 1
		elif issubsequence('1001', S) == True or issubsequence('0110', S) == True or issubsequence('1010', S) == True or (issubsequence('0101', S) == True):
			ans = 2
		elif p == 1 or p == N - 1:
			ans = -1
		else:
			ans = 3
	elif N == 2:
		if x % 3 == 0:
			ans = 0
		else:
			ans = -1
	elif x % 3 == 0:
		ans = 0
	elif S == '101':
		ans = 1
	else:
		ans = -1
	print(ans)


from collections import Counter, UserString
mod = lambda n: n % (10 ** 9 + 7)
fc_ = [1]
for i in range(1, 1000001):
	fc_.append(i * fc_[i - 1])
	fc_[i] = mod(fc_[i])

def fact(n):
	return fc_[n]

def printm(n):
	print(mod(n))

def yn(b, caps=False):
	if b:
		returning = 'Yes'
	else:
		returning = 'No'
	if caps:
		return returning.upper()
	return returning

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

def rounded(n):
	return int(ans) + int(int(ans) != ans)

class mutableStr(UserString):

	def ins(self, n, s):
		if n < 0:
			self.data = self.data = ''.join(list(self.data)[:n + 1]) + s + ''.join(list(self.data)[n + 1:])
		else:
			self.data = ''.join(list(self.data)[:n]) + s + ''.join(list(self.data)[n:])

	def rem(self, s):
		self.data = self.data.replace(s, '')
alphabetOrd = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
binToInt = lambda b: int(str(b), 2)
r2 = lambda n: range(1, n + 1)
alph = lambda s: s.isalpha()
sl = lambda l: list(set(l))
inf = float('inf')
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : mutableStr(input())
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for t in range(int(input())):
	binStr = si()
	intStr = binToInt(binStr)
	if binStr.count('1') == 1:
		print(-1)
		continue
	div = intStr % 3
	if not div:
		print(0)
		continue
	check = []
	binStr = binStr[::-1]
	for i in range(len(binStr)):
		if i % 2 == 1 and binStr[i] == '1':
			check.append(2)
		else:
			check.append(int(binStr[i]))
	singleOp = False
	for i in range(len(check) - 1):
		if check[i] == 3 - div and check[i + 1] == 0 or (check[i + 1] == 3 - div and check[i] == 0):
			singleOp = True
	if singleOp:
		print(1)
	else:
		ans = 0
		for i in range(len(check)):
			if not check[i] and (i > 0 and check[i - 1] == div or (i < len(check) - 1 and check[i + 1] == div)):
				ans += 1
		if ans >= 2:
			print(2)
		elif '1100' in binStr or '0011' in binStr:
			print(3)
		else:
			print(-1)


t = int(input())
for i in range(t):
	s = input()
	o = e = 0
	n = len(s)
	for i in range(n):
		if s[i] == '1':
			if i % 2 == 0:
				e += 1
			else:
				o += 1
	if abs(o - e) % 3 == 0:
		print(0)
	else:
		c = d = 0
		for i in range(1, n):
			if s[i] != s[i - 1]:
				c += 1
		if c == 1:
			for i in range(1, n):
				if (i % 2 == 1 or (n - i) % 2 == 1) and s[i] != s[i - 1] and (i != 1) and (i != n - 1):
					print(3)
					d = 1
					break
		if d == 1:
			continue
		if abs(e - o) % 3 == 2:
			if e + o == n:
				print(-1)
			else:
				print(1)
		elif e + o > n - 1:
			print(-1)
		else:
			f = 0
			for i in range(n):
				if e > o:
					if i % 2 != 0 and s[i] == '1':
						if i - 1 >= 0 and s[i - 1] == '0':
							f = 1
							break
						if i + 1 < n and s[i + 1] == '0':
							f = 1
							break
				elif i % 2 == 0 and s[i] == '1':
					if i - 1 >= 0 and s[i - 1] == '0':
						f = 1
						break
					if i + 1 < n and s[i + 1] == '0':
						f = 1
						break
			if f == 1:
				print(1)
			elif o + e == n - 1:
				print(-1)
			elif o > e:
				cnt = 1 + n // 2
				if o < 2 or cnt < 2:
					print(-1)
				else:
					print(2)
			else:
				cnt = n // 2
				if e < 2 or cnt < 2:
					print(-1)
				else:
					print(2)


for _ in range(int(input())):
	s = input()
	n = len(s)
	(o, e) = (0, 0)
	for i in range(n):
		if s[i] == '1':
			if i % 2 == 0:
				e += 1
			else:
				o += 1
	if abs(o - e) % 3 == 0:
		print(0)
	else:
		(f, x) = (0, 0)
		for i in range(1, n):
			if s[i] != s[i - 1]:
				f += 1
		if f == 1:
			for i in range(1, n):
				if (i % 2 == 1 or (n - i) % 2 == 1) and s[i] != s[i - 1] and (i != 1) and (i != n - 1):
					print(3)
					x = 1
					break
		if x == 1:
			continue
		if abs(e - o) % 3 == 2:
			if e + o == n:
				print(-1)
			else:
				print(1)
		elif e + o > n - 1:
			print(-1)
		else:
			fl = False
			for i in range(n):
				if e > o:
					if i % 2 != 0 and s[i] == '1':
						if i - 1 >= 0 and s[i - 1] == '0':
							fl = True
							break
						if i + 1 < n and s[i + 1] == '0':
							fl = True
							break
				elif i % 2 == 0 and s[i] == '1':
					if i - 1 >= 0 and s[i - 1] == '0':
						fl = True
						break
					if i + 1 < n and s[i + 1] == '0':
						fl = True
						break
			if fl == True:
				print(1)
			elif o + e == n - 1:
				print(-1)
			elif o > e:
				ct = 1 + n // 2
				if o < 2 or ct < 2:
					print(-1)
				else:
					print(2)
			else:
				ct = n // 2
				if e < 2 or ct < 2:
					print(-1)
				else:
					print(2)


for _ in range(int(input())):
	string = input()
	even = 0
	odd = 0
	LENGTH = len(string)
	for I in range(LENGTH):
		if string[I] == '1':
			if I % 2 == 0:
				even += 1
			else:
				odd += 1
	if abs(odd - even) % 3 == 0:
		print(0)
	else:
		counter1 = 0
		counter2 = 0
		for A in range(1, LENGTH):
			if string[A] != string[A - 1]:
				counter1 += 1
		if counter1 == 1:
			for B in range(1, LENGTH):
				if (B % 2 == 1 or (LENGTH - B) % 2 == 1) and string[B] != string[B - 1] and (B != 1) and (B != LENGTH - 1):
					print(3)
					counter2 = 1
					break
		if counter2 == 1:
			continue
		if abs(even - odd) % 3 == 2:
			if even + odd == LENGTH:
				print(-1)
			else:
				print(1)
		elif even + odd > LENGTH - 1:
			print(-1)
		else:
			counter3 = 0
			for C in range(LENGTH):
				if even > odd:
					if C % 2 != 0 and string[C] == '1':
						if C - 1 >= 0 and string[C - 1] == '0':
							counter3 = 1
							break
						elif C + 1 < LENGTH and string[C + 1] == '0':
							counter3 = 1
							break
				elif C % 2 == 0 and string[C] == '1':
					if C - 1 >= 0 and string[C - 1] == '0':
						counter3 = 1
						break
					elif C + 1 < LENGTH and string[C + 1] == '0':
						counter3 = 1
						break
			if counter3 == 1:
				print(1)
			elif even + odd == LENGTH - 1:
				print(-1)
			elif odd > even:
				counter1 = 1 + LENGTH // 2
				if odd < 2 or counter1 < 2:
					print(-1)
				else:
					print(2)
			else:
				counter1 = LENGTH // 2
				if even < 2 or counter1 < 2:
					print(-1)
				else:
					print(2)


def helper(temp, var1, var2, string_len):
	if temp == 1:
		print(1)
	elif var1 + var2 == string_len - 1:
		print(-1)
	elif var1 > var2:
		cnt = 1 + string_len // 2
		if var1 < 2 or cnt < 2:
			print(-1)
		else:
			print(2)
	else:
		cnt = string_len // 2
		if var2 < 2 or cnt < 2:
			print(-1)
		else:
			print(2)

def complete_compare(var1, var2, string_len, string):
	if abs(var2 - var1) % 3 == 2:
		if var2 + var1 == string_len:
			print(-1)
		else:
			print(1)
	elif var2 + var1 > string_len - 1:
		print(-1)
	else:
		temp = 0
		for i in range(string_len):
			if var2 > var1:
				if i % 2 != 0 and string[i] == '1':
					if i - 1 >= 0 and string[i - 1] == '0':
						temp = 1
						break
					if i + 1 < string_len and string[i + 1] == '0':
						temp = 1
						break
			elif i % 2 == 0 and string[i] == '1':
				if i - 1 >= 0 and string[i - 1] == '0':
					temp = 1
					break
				if i + 1 < string_len and string[i + 1] == '0':
					temp = 1
					break
		helper(temp, var1, var2, string_len)

def solution(tri):
	for t in range(tri):
		string = input()
		var1 = var2 = 0
		string_len = len(string)
		for i in range(string_len):
			if string[i] == '1':
				if i % 2 == 0:
					var2 += 1
				else:
					var1 += 1
		if abs(var1 - var2) % 3 == 0:
			print(0)
		else:
			var3 = var4 = 0
			for i in range(1, string_len):
				if string[i] != string[i - 1]:
					var3 += 1
			if var3 == 1:
				for i in range(1, string_len):
					if (i % 2 == 1 or (string_len - i) % 2 == 1) and string[i] != string[i - 1] and (i != 1) and (i != string_len - 1):
						print(3)
						var4 = 1
						break
			if var4 == 1:
				continue
			complete_compare(var1, var2, string_len, string)
trie = int(input())
solution(trie)


t = int(input())
for _ in range(t):
	s = input()
	oo = 0
	eo = 0
	n = len(s)
	ozo = 0
	ezo = 0
	l = [False] * n
	if s[0] == '1':
		eo += 1
	if s[0] == '1' and s[1] == '0':
		ozo += 1
		l[1] = True
	for i in range(1, n):
		if s[i] == '1':
			if i & 1:
				oo += 1
				if s[i - 1] == '0' and l[i - 1] == False:
					ezo += 1
					l[i - 1] = True
				elif i < n - 1:
					if s[i + 1] == '0' and l[i + 1] == False:
						ezo += 1
						l[i + 1] = True
			else:
				eo += 1
				if s[i - 1] == '0' and l[i - 1] == False:
					ozo += 1
					l[i - 1] = True
				elif i < n - 1:
					if s[i + 1] == '0' and l[i + 1] == False:
						ozo += 1
						l[i + 1] = True
	dif = abs(oo - eo)
	m = dif % 3
	if m == 0:
		print(0)
		continue
	c = d = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			c += 1
	if c == 1:
		for i in range(1, n):
			if i & 1 and s[i] != s[i - 1] and (i != 1) and (i != n - 1):
				print(3)
				d = 1
				break
	if d == 1:
		continue
	if m == 1:
		if oo < eo:
			if ezo >= 1 and oo > 0:
				print(1)
			elif ozo >= 2 and eo > 1:
				print(2)
			else:
				print(-1)
		elif ozo >= 1 and eo > 0:
			print(1)
		elif ezo >= 2 and oo > 1:
			print(2)
		else:
			print(-1)
	elif oo > eo:
		if ezo >= 1 and oo > 0:
			print(1)
		elif ozo >= 2 and eo > 1:
			print(2)
		else:
			print(-1)
	elif ozo >= 1 and eo > 0:
		print(1)
	elif ezo >= 2 and oo > 1:
		print(2)
	else:
		print(-1)


import math

def solve(s):
	op = ep = 0
	for i in range(len(s)):
		if s[i] == '1':
			if i & 1:
				op += 1
			else:
				ep += 1
	if abs(op - ep) % 3 == 0:
		return 0
	diff = 0
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			diff += 1
	n = len(s)
	if diff == 1:
		for i in range(1, len(s)):
			if (i % 2 != 0 or (len(s) - i) % 2 != 0) and s[i] != s[i - 1] and (i != 1) and (i != len(s) - 1):
				return 3
	if abs(op - ep) % 3 == 2:
		if op + ep == len(s):
			return -1
		return 1
	if op + ep > len(s) - 1:
		return -1
	flag = False
	for i in range(len(s)):
		if ep > op:
			if (i & 1 and s[i] == '1') and (i - 1 >= 0 and s[i - 1] == '0' or (i + 1 < len(s) and s[i + 1] == '0')):
				flag = True
				break
		elif not i & 1 and s[i] == '1':
			if i - 1 >= 0 and s[i - 1] == '0' or (i + 1 < len(s) and s[i + 1] == '0'):
				flag = True
				break
	if flag:
		return 1
	if op + ep == n - 1:
		return -1
	if op > ep:
		if op < 2:
			return -1
		c = 0
		for i in range(len(s)):
			if i % 2 == 0:
				c += 1
		if c < 2:
			return -1
		return 2
	c = 0
	for i in range(len(s)):
		if i & 1:
			c += 1
	if ep < 2 or c < 2:
		return -1
	return 2
t = int(input())
ans = []
for i in range(t):
	s = input()
	ans.append(solve(s))
for i in ans:
	try:
		print(*i)
	except:
		print(i)


from math import factorial
from collections import Counter, defaultdict

class Solution:

	def fact(self, n, dp):
		if n == 1:
			return 1
		if dp[n]:
			return dp[n]
		dp[n] = n * self.fact(n - 1, dp)
		return dp[n]

	def splitingBalls(self, n, bolls, dp):
		ans = 0
		freq = Counter(bolls)
		for (bol, val) in freq.items():
			ans += val * self.fact(bol, dp)
		return ans % (10 ** 9 + 7)

	def swap(self, n, s):
		orig = end = 0
		for i in range(n):
			if s[i] == '1':
				if i % 2 == 0:
					end += 1
				else:
					orig += 1
		if abs(orig - end) % 3 == 0:
			return 0
		else:
			fog = mog = 0
			for i in range(1, n):
				if s[i] != s[i - 1]:
					fog += 1
			if fog == 1:
				for i in range(1, n):
					if i % 2 == 1 or (n - 1 % 2 == 1 and s[i] != s[i - 1] and (i != 1) and (i != n - 1)):
						return 3
						d = 1
						break
			if mog == 1:
				return
			if abs(end - orig) % 3 == 2:
				if end + orig == n:
					return -1
				else:
					return 1
			elif end + orig > n - 1:
				return -1
			else:
				lag = 0
				for i in range(n):
					if end <= orig:
						if i % 2 == 0 and s[i] == '1':
							if i + 1 < n and s[i + 1] == '0':
								lag = 1
								break
							if i - 1 >= 0 and s[i - 1] == '0':
								lag = 1
								break
					elif i % 2 != 0 and s[i] == '1':
						if i + 1 < n and s[i + 1] == '0':
							lag = 1
							break
						if i - 1 >= 0 and s[i - 1] == '0':
							lag = 1
							break
				if lag == 1:
					return 1
				elif orig + end == n - 1:
					return -1
				elif orig > end:
					cnt = 1 + n // 2
					if orig < 2 or cnt < 2:
						return -1
					else:
						return 2
				else:
					cnt = n // 2
					if end < 2 or cnt < 2:
						return -1
					else:
						return 2
for i in range(int(input())):
	s = input()
	orig = end = 0
	n = len(s)
	for i in range(n):
		if s[i] == '1':
			if i % 2 == 0:
				end += 1
			else:
				orig += 1
	if abs(orig - end) % 3 == 0:
		print(0)
	else:
		fog = mog = 0
		for i in range(1, n):
			if s[i] != s[i - 1]:
				fog += 1
		if fog == 1:
			for i in range(1, n):
				if (i % 2 == 1 or (n - 1) % 2 == 1) and s[i] != s[i - 1] and (i != 1) and (i != n - 1):
					print(3)
					mog = 1
					break
		if mog == 1:
			continue
		if abs(end - orig) % 3 == 2:
			if end + orig == n:
				print(-1)
			else:
				print(1)
		elif end + orig > n - 1:
			print(-1)
		else:
			lag = 0
			for i in range(n):
				if end <= orig:
					if i % 2 == 0 and s[i] == '1':
						if i + 1 < n and s[i + 1] == '0':
							lag = 1
							break
						if i - 1 >= 0 and s[i - 1] == '0':
							lag = 1
							break
				elif i % 2 != 0 and s[i] == '1':
					if i + 1 < n and s[i + 1] == '0':
						lag = 1
						break
					if i - 1 >= 0 and s[i - 1] == '0':
						lag = 1
						break
			if lag == 1:
				print(1)
			elif orig + end == n - 1:
				print(-1)
			elif orig > end:
				cnt = 1 + n // 2
				if orig < 2 or cnt < 2:
					print(-1)
				else:
					print(2)
			else:
				cnt = n // 2
				if end < 2 or cnt < 2:
					print(-1)
				else:
					print(2)


try:
	T = int(input())
	for i in range(T):
		s = input()
		a = b = 0
		l = len(s)
		for i in range(l):
			if s[i] == '1':
				if i % 2 == 0:
					b += 1
				else:
					a += 1
		if abs(a - b) % 3 == 0:
			print(0)
		else:
			c = d = 0
			for i in range(1, l):
				if s[i] != s[i - 1]:
					c += 1
			if c == 1:
				for i in range(1, l):
					if (i % 2 == 1 or (l - i) % 2 == 1) and s[i] != s[i - 1] and (i != 1) and (i != l - 1):
						print(3)
						d = 1
						break
			if d == 1:
				continue
			if abs(b - a) % 3 == 2:
				if b + a == l:
					print(-1)
				else:
					print(1)
			elif b + a > l - 1:
				print(-1)
			else:
				f = 0
				for i in range(l):
					if b > a:
						if i % 2 != 0 and s[i] == '1':
							if i - 1 >= 0 and s[i - 1] == '0':
								f = 1
								break
							if i + 1 < l and s[i + 1] == '0':
								f = 1
								break
					elif i % 2 == 0 and s[i] == '1':
						if i - 1 >= 0 and s[i - 1] == '0':
							f = 1
							break
						if i + 1 < l and s[i + 1] == '0':
							f = 1
							break
				if f == 1:
					print(1)
				elif a + b == l - 1:
					print(-1)
				elif a > b:
					x = 1 + l // 2
					if a < 2 or x < 2:
						print(-1)
					else:
						print(2)
				else:
					x = l // 2
					if b < 2 or x < 2:
						print(-1)
					else:
						print(2)
except:
	pass


for _ in range(int(input())):
	S = str(input())
	n = len(S)
	c = 0
	o = e = 0
	for i in range(n):
		if S[i] == '1':
			if i % 2:
				o += 1
			else:
				e += 1
	if abs(e - o) % 3 == 0:
		print(0)
	else:
		f = x = 0
		for i in range(1, n):
			if S[i] != S[i - 1]:
				f += 1
		if f == 1:
			for i in range(1, n):
				if (i % 2 or (n - i) % 2) and S[i] != S[i - 1] and (i != 1) and (i != n - 1):
					print(3)
					x = 1
					break
			if x:
				continue
		if abs(o - e) % 3 == 2:
			if e + o == n:
				print(-1)
			else:
				print(1)
		elif e + o > n - 1:
			print(-1)
		else:
			f = 0
			for i in range(n):
				if e > o:
					if i % 2 and S[i] == '1':
						if i - 1 >= 0 and S[i - 1] == '0':
							f = 1
							break
						if i + 1 < n and S[i + 1] == '0':
							f = 1
							break
				elif i % 2 == 0 and S[i] == '1':
					if i - 1 >= 0 and S[i - 1] == '0':
						f = 1
						break
					if i + 1 < n and S[i + 1] == '0':
						f = 1
						break
			if f:
				print(1)
			elif e + o == n - 1:
				print(-1)
			elif o > e:
				ctt = 0
				for i in range(n):
					if i % 2 == 0:
						ctt += 1
				if o < 2 or ctt < 2:
					print(-1)
				else:
					print(2)
			else:
				ctt = 0
				for i in range(n):
					if i % 2:
						ctt += 1
				if e < 2 or ctt < 2:
					print(-1)
				else:
					print(2)


t = int(input())
for i in range(t):
	s = input()
	odd = even = 0
	n = len(s)
	for j in range(n):
		if s[j] == '1':
			if j % 2 == 0:
				even += 1
			else:
				odd += 1
	if abs(odd - even) % 3 == 0:
		print(0)
	else:
		c = d = 0
		for j in range(1, n):
			if s[j] != s[j - 1]:
				c += 1
		if c == 1:
			for i in range(1, n):
				if (i % 2 == 1 or (n - i) % 2 == 1) and s[i] != s[i - 1] and (i != 1) and (i != n - 1):
					print(3)
					d = 1
					break
		if d == 1:
			continue
		if abs(even - odd) % 3 == 2:
			if even + odd == n:
				print(-1)
			else:
				print(1)
		elif even + odd > n - 1:
			print(-1)
		else:
			f = 0
			for i in range(n):
				if even > odd:
					if i % 2 != 0 and s[i] == '1':
						if i - 1 >= 0 and s[i - 1] == '0':
							f = 1
							break
						if i + 1 < n and s[i + 1] == '0':
							f = 1
							break
				elif i % 2 == 0 and s[i] == '1':
					if i - 1 >= 0 and s[i - 1] == '0':
						f = 1
						break
					if i + 1 < n and s[i + 1] == '0':
						f = 1
						break
			if f == 1:
				print(1)
			elif odd + even == n - 1:
				print(-1)
			elif odd > even:
				count = 1 + n // 2
				if odd < 2 or count < 2:
					print(-1)
				else:
					print(2)
			else:
				count = n // 2
				if even < 2 or count < 2:
					print(-1)
				else:
					print(2)


for _ in range(int(input())):
	s = input()
	n = len(s)
	(even, odd) = (0, 0)
	for i in range(n):
		if s[i] == '1':
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
	if abs(odd - even) % 3 == 0:
		print(0)
	else:
		(count, d) = (0, 0)
		for i in range(1, n):
			if s[i] != s[i - 1]:
				count += 1
		if count == 1:
			for i in range(1, n):
				if (i % 2 == 1 or (n - i) % 2 == 1) and s[i] != s[i - 1] and (i != 1) and (i != n - 1):
					print(3)
					d = 1
					break
		if d == 1:
			continue
		if abs(odd - even) % 3 == 2:
			if odd + even == n:
				print(-1)
			else:
				print(1)
		elif even + odd > n - 1:
			print(-1)
		else:
			f = 0
			for i in range(n):
				if even > odd:
					if i % 2 != 0 and s[i] == '1':
						if i - 1 >= 0 and s[i - 1] == '0':
							f = 1
							break
						if i + 1 < n and s[i + 1] == '0':
							f = 1
							break
				elif i % 2 == 0 and s[i] == '1':
					if i - 1 >= 0 and s[i - 1] == '0':
						f = 1
						break
					if i + 1 < n and s[i + 1] == '0':
						f = 1
						break
			if f == 1:
				print(1)
			elif odd + even == n - 1:
				print(-1)
			elif odd > even:
				p = 1 + n // 2
				if odd < 2 or p < 2:
					print(-1)
				else:
					print(2)
			else:
				p = n // 2
				if even < 2 or p < 2:
					print(-1)
				else:
					print(2)


for t in range(int(input())):
	s = input()
	ec = 0
	oc = 0
	for i in range(len(s)):
		if i % 2 == 0 and s[i] == '1':
			ec += 1
		elif i % 2 != 0 and s[i] == '1':
			oc += 1
	val = abs(oc - ec) % 3
	if val == 0:
		print('0')
	else:
		(temp, temp1) = (0, 0)
		for i in range(1, len(s)):
			if s[i] != s[i - 1]:
				temp += 1
		if temp == 1:
			for i in range(1, len(s)):
				if (i % 2 == 1 or (len(s) - i) % 2 == 1) and s[i] != s[i - 1] and (i != 1 and i != len(s) - 1):
					print('3')
					temp1 = 1
					break
			if temp1 == 1:
				continue
		if val == 2:
			if ec + oc == len(s):
				print('-1')
			else:
				print('1')
		elif ec + oc > len(s) - 1:
			print('-1')
		else:
			ans = False
			for i in range(len(s)):
				if ec > oc:
					if i % 2 != 0 and s[i] == '1':
						if i - 1 >= 0 and s[i - 1] == '0':
							ans = True
							break
						if i + 1 < len(s) and s[i + 1] == '0':
							ans = True
							break
				elif i % 2 == 0 and s[i] == '1':
					if i - 1 >= 0 and s[i - 1] == '0':
						ans = True
						break
					if i + 1 < len(s) and s[i + 1] == '0':
						ans = True
						break
			if ans:
				print('1')
			elif oc + ec == len(s) - 1:
				print('-1')
			else:
				tempp = 0
				if oc > ec:
					for i in range(len(s)):
						if i % 2 == 0:
							tempp += 1
					if oc < 2 or tempp < 2:
						print('-1')
					else:
						print('2')
				else:
					temppp = 0
					for i in range(len(s)):
						if i % 2 != 0:
							temppp += 1
					if ec < 2 or temppp < 2:
						print('-1')
					else:
						print('2')


for i in range(int(input())):
	stri = input()
	odd_ = even_ = 0
	nen = len(stri)
	for i in range(nen):
		if stri[i] == '1':
			if i % 2 == 0:
				even_ += 1
			else:
				odd_ += 1
	if abs(odd_ - even_) % 3 == 0:
		print(0)
	else:
		cx = dx = 0
		for i in range(1, nen):
			if stri[i] != stri[i - 1]:
				cx += 1
		if cx == 1:
			for i in range(1, nen):
				if (i % 2 == 1 or (nen - i) % 2 == 1) and stri[i] != stri[i - 1] and (i != 1) and (i != nen - 1):
					print(3)
					dx = 1
					break
		if dx == 1:
			continue
		if abs(even_ - odd_) % 3 == 2:
			if even_ + odd_ == nen:
				print(-1)
			else:
				print(1)
		elif even_ + odd_ > nen - 1:
			print(-1)
		else:
			flagi = 0
			for i in range(nen):
				if even_ > odd_:
					if i % 2 != 0 and stri[i] == '1':
						if i - 1 >= 0 and stri[i - 1] == '0':
							flagi = 1
							break
						if i + 1 < nen and stri[i + 1] == '0':
							flagi = 1
							break
				elif i % 2 == 0 and stri[i] == '1':
					if i - 1 >= 0 and stri[i - 1] == '0':
						flagi = 1
						break
					if i + 1 < nen and stri[i + 1] == '0':
						flagi = 1
						break
			if flagi == 1:
				print(1)
			elif odd_ + even_ == nen - 1:
				print(-1)
			elif odd_ > even_:
				count = 1 + nen // 2
				if odd_ < 2 or count < 2:
					print(-1)
				else:
					print(2)
			else:
				count = nen // 2
				if even_ < 2 or count < 2:
					print(-1)
				else:
					print(2)


def solve():
	s = input()
	o = 0
	e = 0
	for i in range(len(s)):
		if s[i] == '1':
			if i & 1:
				o += 1
			else:
				e += 1
	if abs(o - e) % 3 == 0:
		print(0)
		return
	f = 0
	x = 0
	n = len(s)
	for i in range(1, n):
		if s[i] != s[i - 1]:
			f += 1
	if f == 1:
		for i in range(1, n):
			if (i & 1 or n - i & 1) and s[i] != s[i - 1] and (i != 1) and (i != n - 1):
				print(3)
				return
	if abs(o - e) % 3 == 2:
		if o + e == n:
			print(-1)
		else:
			print(1)
	elif o + e > n - 1:
		print(-1)
	else:
		b = False
		for i in range(n):
			if e > o:
				if i % 2 != 0 and s[i] == '1':
					if i - 1 >= 0 and s[i - 1] == '0':
						b = True
						break
					if i + 1 < n and s[i + 1] == '0':
						b = True
						break
			elif i % 2 == 0 and s[i] == '1':
				if i - 1 >= 0 and s[i - 1] == '0':
					b = True
					break
				if i + 1 < n and s[i + 1] == '0':
					b = True
					break
		if b:
			print(1)
		elif o + e == n - 1:
			print(-1)
		elif o > e:
			c = 0
			for i in range(n):
				if i % 2 == 0:
					c += 1
			if o < 2 or c < 2:
				print(-1)
			else:
				print(2)
		else:
			c = 0
			for i in range(n):
				if i % 2 != 0:
					c += 1
			if e < 2 or c < 2:
				print(-1)
			else:
				print(2)

def main():
	for _ in range(int(input())):
		solve()
main()


import math

def p(madarchod_cc_xx):
	if madarchod_cc_xx <= 1:
		return False
	elif madarchod_cc_xx == 2:
		return True
	for madarchod_cc_ii in range(2, int(math.sqrt(madarchod_cc_xx)) + 1):
		if madarchod_cc_xx % madarchod_cc_ii == 0:
			return False
	return True

def madarchod_cc_ans(madarchod_cc_ss, madarchod_cc_ll, madarchod_cc_ee, madarchod_cc_oo):
	if abs(madarchod_cc_oo - madarchod_cc_ee) % 3 == 0:
		return 0
	(madarchod_cc_xx, madarchod_cc_yy) = (0, 0)
	for madarchod_cc_ii in range(1, madarchod_cc_ll):
		if madarchod_cc_ss[madarchod_cc_ii] != madarchod_cc_ss[madarchod_cc_ii - 1]:
			madarchod_cc_yy += 1
	if madarchod_cc_yy == 1:
		for madarchod_cc_ii in range(1, madarchod_cc_ll):
			if (madarchod_cc_ii & 1 != 0 or madarchod_cc_ll - madarchod_cc_ii & 1 != 0) and madarchod_cc_ss[madarchod_cc_ii] != madarchod_cc_ss[madarchod_cc_ii - 1] and (madarchod_cc_ii != 1) and (madarchod_cc_ii != madarchod_cc_ll - 1):
				return 3
	if abs(madarchod_cc_ee - madarchod_cc_oo) % 3 == 2:
		if madarchod_cc_oo + madarchod_cc_ee == madarchod_cc_ll:
			return -1
		else:
			return 1
	if madarchod_cc_oo + madarchod_cc_ee > madarchod_cc_ll - 1:
		return -1
	else:
		chk = False
		for madarchod_cc_ii in range(madarchod_cc_ll):
			if madarchod_cc_ee > madarchod_cc_oo:
				if madarchod_cc_ii % 2 != 0 and madarchod_cc_ss[madarchod_cc_ii] == '1':
					if madarchod_cc_ii - 1 >= 0 and madarchod_cc_ss[madarchod_cc_ii - 1] == '0':
						chk = True
						break
					if madarchod_cc_ii + 1 < madarchod_cc_ll and madarchod_cc_ss[madarchod_cc_ii + 1] == '0':
						chk = True
						break
			elif madarchod_cc_ii % 2 == 0 and madarchod_cc_ss[madarchod_cc_ii] == '1':
				if madarchod_cc_ii - 1 >= 0 and madarchod_cc_ss[madarchod_cc_ii - 1] == '0':
					chk = True
					break
				if madarchod_cc_ii + 1 < madarchod_cc_ll and madarchod_cc_ss[madarchod_cc_ii + 1] == '0':
					chk = True
					break
		if chk:
			return 1
		elif madarchod_cc_oo + madarchod_cc_ee == madarchod_cc_ll - 1:
			return -1
		elif madarchod_cc_oo > madarchod_cc_ee:
			madarchod_cc_cnt = 0
			for madarchod_cc_ii in range(madarchod_cc_ll):
				if madarchod_cc_ii % 2 == 0:
					madarchod_cc_cnt += 1
			if madarchod_cc_oo < 2 or madarchod_cc_cnt < 2:
				return -1
			else:
				return 2
		else:
			madarchod_cc_cnt = 0
			for madarchod_cc_ii in range(madarchod_cc_ll):
				if madarchod_cc_ii % 2 != 0:
					madarchod_cc_cnt += 1
			if madarchod_cc_ee < 2 or madarchod_cc_cnt < 2:
				return -1
			else:
				return 2
for madarchod_cc in range(int(input())):
	madarchod_cc_ss = input()
	madarchod_cc_ll = len(madarchod_cc_ss)
	(madarchod_cc_ee, madarchod_cc_oo) = (0, 0)
	for madarchod_cc_ii in range(madarchod_cc_ll):
		if madarchod_cc_ss[madarchod_cc_ii] == '1':
			if madarchod_cc_ii & 1 != 0:
				madarchod_cc_oo += 1
			else:
				madarchod_cc_ee += 1
	print(madarchod_cc_ans(madarchod_cc_ss, madarchod_cc_ll, madarchod_cc_ee, madarchod_cc_oo))


def mod_three(s):
	res = 0
	p = 1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '1':
			res = (res + p) % 3
		p = p * 2 % 3
	return res

def f(s):
	val = mod_three(s)
	if val == 0:
		return 0
	ones = 0
	twos = 0
	doubles = 0
	threes = 0
	special_index = None
	if s[0] == '0':
		for i in range(len(s)):
			if s[i] == '1':
				if i + 1 < len(s) and s[i + 1] == '0':
					special_index = i
				break
	p1 = 1
	p2 = None
	for i in range(len(s) - 1, -1, -1):
		v_right = set()
		v_left = set()
		if i == special_index:
			if 3 - p2 == 1:
				ones += 1
			elif 3 - p2 == 2:
				twos += 1
		if s[i] == '0' and i < len(s) - 1 and (s[i + 1] == '0') and (i > 1) and (s[i - 1] == '1') and (s[i - 2] == '1'):
			threes += 1
		if s[i] == '0' and i < len(s) - 2 and (s[i + 1] == '1') and (s[i + 2] == '1') and (i > 0) and (s[i - 1] == '0'):
			threes += 1
		if s[i] == '0' and i < len(s) - 1 and (s[i + 1] == '1') and (i + 1 != special_index):
			if p2 == 1:
				v_right.add(1)
			elif p2 == 2:
				v_right.add(2)
		if s[i] == '0' and i > 0 and (s[i - 1] == '1') and (i - 1 != special_index):
			if 3 - p1 == 1:
				v_left.add(1)
			elif 3 - p1 == 2:
				v_left.add(2)
		vs = v_right | v_left
		if len(vs) == 2:
			doubles += 1
		elif 1 in vs:
			ones += 1
		elif 2 in vs:
			twos += 1
		p1 = p1 * 2 % 3
		if p2 is None:
			p2 = 1
		else:
			p2 = p2 * 2 % 3
	if val == 1 and twos + doubles > 0 or (val == 2 and ones + doubles > 0):
		return 1
	if val == 2 and twos + doubles > 1 or (val == 1 and ones + doubles > 1):
		return 2
	if threes > 0:
		return 3
	return -1
t = int(input())
for i in range(t):
	s = input()
	print(f(s))


t = int(input())
for _ in range(t):
	S = [int(i) for i in list(input())]
	n = len(S)
	o = 0
	e = 0
	x = 0
	y = 0
	for i in range(n):
		if i % 2 == 0 and S[i] == 1:
			o += 1
		elif i % 2 == 1 and S[i] == 1:
			e += 1
		if i % 2 == 1 and S[i] == 0:
			try:
				if S[i - 1] == 1 or S[i + 1] == 1:
					x += 1
			except:
				if S[i - 1] == 1:
					x += 1
		elif i % 2 == 0 and S[i] == 0:
			if i == 0:
				if S[i + 1] == 1:
					y += 1
			elif i == n - 1:
				if S[i - 1] == 1:
					y += 1
			elif S[i - 1] == 1 or S[i + 1] == 1:
				y += 1
	if (o - e) % 3 == 0:
		print(0)
	elif o == 1 and e == 0 or (o == 0 and e == 1):
		print(-1)
	elif min(o, e) == 0:
		k = max(o, e)
		if (k - 2) % 3 == 0:
			print(1)
		else:
			print(2)
	elif (o - e - 2) % 3 == 0:
		if x > 0:
			print(1)
		elif y > 1:
			print(2)
		elif n - (o + e) > 1:
			print(3)
		else:
			print(-1)
	elif y > 0:
		print(1)
	elif x > 1:
		print(2)
	elif n - (o + e) > 1:
		print(3)
	else:
		print(-1)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	eo = 0
	oo = 0
	ez = 0
	oz = 0
	o = 0
	e = 0
	for i in range(n):
		if i % 2 == 0:
			if s[i] == '1':
				eo += 1
				if i + 1 < n and s[i + 1] == '0':
					e += 1
			else:
				if i + 1 < n and s[i + 1] == '1':
					o += 1
				ez += 1
		elif s[i] == '1':
			oo += 1
			if i + 1 < n and s[i + 1] == '0':
				o += 1
		else:
			if i + 1 < n and s[i + 1] == '1':
				e += 1
			oz += 1
	m = -1
	if abs(oo - eo) % 3 == 0:
		print(0)
	else:
		if eo >= 1 and oz >= 1 and (e >= 1):
			if abs(oo + 1 - (eo - 1)) % 3 == 0:
				m = 1
		if oo >= 1 and ez >= 1 and (o >= 1):
			if abs(oo - 1 - (eo + 1)) % 3 == 0:
				m = 1
		if eo >= 2 and oz >= 2 and (m == -1) and (e >= 2):
			if abs(oo + 2 - (eo - 2)) % 3 == 0:
				m = 2
		if oo >= 2 and ez >= 2 and (m == -1) and (o >= 2):
			if abs(oo - 2 - (eo + 2)) % 3 == 0:
				m = 2
		if m == -1 and eo >= 1 and (oz >= 1):
			if abs(oo + 1 - (eo - 1)) % 3 == 0:
				m = 3
		if m == -1 and oo >= 1 and (ez >= 1):
			if abs(oo - 1 - (eo + 1)) % 3 == 0:
				m = 3
		print(m)


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

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
for t in range(int(input())):
	s = str(input())
	if s.count('1') == 1:
		print(-1)
		continue
	n = int(s, 2)
	mod = n % 3
	if mod == 0:
		print(0)
		continue
	a = []
	s = s[::-1]
	for i in range(len(s)):
		if i % 2 == 1 and s[i] == '1':
			a.append(2)
		else:
			a.append(int(s[i]))
	flag = False
	for i in range(len(a) - 1):
		if a[i] == 3 - mod and a[i + 1] == 0 or (a[i + 1] == 3 - mod and a[i] == 0):
			flag = True
	if flag:
		print(1)
	else:
		count = 0
		for i in range(len(a)):
			if a[i] == 0:
				if i > 0 and a[i - 1] == mod or (i < len(a) - 1 and a[i + 1] == mod):
					count += 1
		if count >= 2:
			print(2)
		elif '1100' in s or '0011' in s:
			print(3)
		else:
			print(-1)