A binary string is called a self-destructing string if it can reduced to an empty string by performing the following operation some number of times (possibly zero): Choose a valid integer $i$ such that the $i$-th character of the current string is different from the $i+1$-th character, and remove these two characters from the string.
You are given a binary string $s$. Your task is to convert $s$ to a self-destructing string. To do that, you may perform the following operation any number of times (possibly zero): Choose an integer $i$ ($1 \le i \le |s|-1$) such that the $i$-th character of $s$ is different from the $i+1$-th character, and invert one of these characters (inverting a character means changing '0' to '1' or '1' to '0', e.g. the string "01" can be changed to "00").
Find the smallest number of operations required to convert $s$ to a self-destructing string or determine that it is impossible.

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

-----Output-----
For each test case, print a single line containing one integer ― the smallest required number of operations or $-1$ if it is impossible to convert $s$ to a self-destructing string.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le |s| \le 10^6$
- $s$ contains only characters '0' and '1'
- the sum of $|s|$ over all test cases does not exceed $10^6$

-----Example Input-----
3
001101
1101
110

-----Example Output-----
0
1
-1

-----Explanation-----
Example case 1: We already have a self-destructing string because "001101" can be converted to "0101", to "01" and finally to an empty string.
Example case 2: We can choose $i=3$ (since $s_3 \neq s_4$) and then invert $s_4$ to obtain "1100", which is a self-destructing string.
Example case 3: It can be shown that "110" cannot be converted to a self-destructing string.

Difficulty: interview

Starter code:

Solutions:
t=int(input())
for i in range(t):
 s=input()
 zeroes=s.count('0')
 ones=s.count('1')
 if (len(s)%2==1 or zeroes==0 or ones==0):
  ans= -1
 else:
  ans=abs(zeroes-ones)//2
 print(ans) 

a = int(input())
for i in range(a):
 b = list(map(int,str(input())))
 if len(b)%2!=0:
  print(-1)
 else:
  if sum(b)==len(b) or sum(b)==0:
   print(-1)
  else:
   print(abs((len(b)//2)-sum(b)))

# cook your dish here
for u in range(int(input())):
 s = input()
 cnt0 = s.count('0')
 cnt1 = s.count('1')
 if len(s)%2 != 0 or cnt0==len(s) or cnt1==len(s):
  print(-1)
 else:
  d = abs(cnt1-cnt0)
  if d == 0:
   print(0)
  else:
   print(d//2) 

# cook your dish here
t=int(input())
while t>0 :
 s=input()
 n=len(s) 
 x=s.count('1')
 if n%2==1 or x==0 or x==n :
  print(-1)
 else :
  print(abs(n//2-x))
 t-=1

for _ in range(int(input())):
 s = input()
 
 
 d = {'0':0, '1':0}
 for i in s:
   d[i] += 1 
 
 if(len(s)%2 or d['1']==0 or d['0'] == 0):
  print(-1)
 else:
  print(abs(d['1'] - d['0']) //2)
   
 


t=int(input())
for i in range(1,t+1):
 st=input()
 a=st.count('0',0,len(st))
 b=st.count('1',0,len(st))
 if len(st)%2==1 or a==0 or b==0:
  ans=-1
 else:
  ans=abs(a-b)//2
 print(ans)


for _ in range(int(input())):
 sg = input().strip()
 l = len(sg)
 if l % 2 != 0:
  print(-1)
 else:
  ones = 0; zeros = 0;
  for i in range(l):
   if sg[i] == '1':
    ones += 1
   else:
    zeros += 1
  diff = abs(ones - zeros)
  if diff == l:
   print(-1)
  else:
   diff //= 2
   print(diff)


for t in range(int(input())):
 s=input()
 z=s.count("0")
 o=s.count("1")
 if len(s)%2==0:
  if z==0 or o==0:
   print(-1)
  else:
   print(len(s)//2-min(o,z))
 else:
  print(-1)

for _ in range(int(input())):
 s = str(input())
 if len(s)&1==1:
  print(-1)
 else:
  z = 0
  o = 0
  for i in range(len(s)):
   if s[i]=='0':
    z+=1
   else:
    o+=1
  if z==o:
   print(0)
  elif (z or o)!=len(s):
   print(int(abs(z-o)/2))
  else:
   print(-1)

# cook your dish here
t=int(input())
for i in range(t):
 l=input()
 if len(l)%2==1:
  print(-1)
 else:
  z=l.count("1")
  s=len(l)
  if s==z or z==0:
   print(-1)
  else:
   print(abs(s-2*z)//2)


for _ in range(int(input())):
 s = input()
 l = len(s)
 if l%2==1:
  print(-1)
 else:
  c1 = s.count('1')
  c0 = l-c1
  if c0 == 0 or c1 == 0:
   print(-1)
  elif c1==c0:
   print(0)
  else:
   print(abs(c1-c0)//2)

# cook your dish here
for _ in range(int(input())):
 s = input()
 lisS = list(s)
 
 if(len(set(lisS))==1 or len(s) % 2 != 0):
  print(-1)
 else:
  mid = len(s) // 2
  numZeros = 0
  for i in range(len(s)):
   if(s[i] == "0"):
    numZeros += 1
  
  print(abs(mid - numZeros))

# 10 + 20 + 2:28



def solve(b,n):
 x=0
 y=0
 for i in range(n):
  if b[i]=='1':
   x+=1
  else:
   y+=1
 if x==n or y==n:
  return -1

 return abs(x-y)//2


for tests in range(int(input())):
 b=input()
 n=len(b)
 if n%2==1:
  print(-1)
 else:
  print(solve(b,n))

# cook your dish here
t=int(input())
for _ in range(t):
 s=list(input())
 n=len(s)
 if(n%2==1):
  print(-1)
 else:
  i=0
  k1=s.count('1')
  k2=s.count('0')
  if(k1==k2):
   print(0)
  elif(k1==0 or k2==0):
   print(-1)
  else:
   kmin=min(k1,k2)
   required=n//2
   print(required-kmin)

# cook your dish here
t=int(input())
for _ in range(t):
 s=list(input())
 n=len(s)
 if(n%2==1):
  print(-1)
 else:
  i=0
  k1=s.count('1')
  k2=s.count('0')
  if(k1==k2):
   print(0)
  elif(k1==0 or k2==0):
   print(-1)
  else:
   kmin=min(k1,k2)
   required=n//2
   print(required-kmin)

for _ in range(int(input())):
 s = input()
 n =len(s)
 if len(s)== s.count("0") or len(s)== s.count("1"):
  print(-1)
 else:
  if n%2==0:
   x =abs(n-2*(s.count("0")))
   print(x//2)
  else:
   print(-1)
  



# cook your dish here
t = int(input())
for _ in range(t):
 s = input()
 x = s.count('0')
 y = s.count('1')
 if (len(s)%2 == 1 or x == 0 or y == 0):
  print(-1)
 else:
  print(abs(x-y)//2)

# cook your dish here
t = int(input())
for _ in range(t):
 s = input();
 a = s.count('0')
 b = s.count('1');
 if(len(s)%2==1 or a==0 or b==0):
  ans = -1
 else:
  ans = abs(a-b)//2;
 print(ans)

# cook your dish here
t = int(input())
for _ in range(t):
 s = input();
 a = s.count('0')
 b = s.count('1');
 if(len(s)%2==1 or a==0 or b==0):
  ans = -1
 else:
  ans = abs(a-b)//2;
 print(ans)

# cook your dish here
t = int(input())
for _ in range(t):
 s = input();
 a = s.count('0')
 b = s.count('1');
 if(len(s)%2==1 or a==0 or b==0):
  ans = -1
 else:
  ans = abs(a-b)//2;
 print(ans)

# cook your dish here
for _ in range(int(input())):
 n=list(input())
 if len(n)%2==1:
  print(-1)
 else:
  s1=n.count('0')
  s2=n.count('1')
  if s1>0 and s2>0:
   print(abs(s1-s2)//2)
  else:
   print(-1)

# cook your dish here
for _ in range(int(input())):
 n=list(input())
 if len(n)%2==1:
  print(-1)
 else:
  s1=n.count('0')
  s2=n.count('1')
  if abs(s1-s2)%2==0 and s1>0 and s2>0:
   print(abs(s1-s2)//2)
  else:
   print(-1)

# cook your dish here
try:
 t = int(input())
 for k in range(t):
  s = input()
  ans = 0
  if((len(s)%2!=0) or (not '0'in s) or (not '1' in s)):
   ans = -1
  else:
   zeros = 0
   ones = 0
   for i in s:
    if i=='1':
     ones += 1 
    else :
     zeros += 1 
   ans = abs(zeros - ones)//2
  print(ans)
except:
 pass
   


a = int(input())
for x in range(a):
 b = input()
 c = b.count("1")
 d = b.count("0")
 if c == len(b) or d == len(b):
  print(-1)
 elif len(b)&1 == 1:
  print(-1)
 else:
  print(int(len(b)/2)-min(c,d))

# cook your dish here
t=int(input())
for i in range(t):
 s=input()
 n=len(s)
 if(n%2==1):
  print(-1)
 else:
  o=s.count('1')
  z=s.count('0')
  if(o==n or z==n):
   print(-1)
  else:
   
   print(n//2-min(o,z))