On his birthday Chef got a string S consisting of only lowercase letters as a goodie from the Techkriti Team. Chef likes strings which have only one kind of character in them. For example, he likes the string "wwww", but does not like the string "aab". 
He is wondering whether he can create such a string from the given string. Unfortunately, he has no scissors, and so he can only tear the string in the middle such that he gets two strings of equal length. ie. if he has a string "abcd", he can tear it and get the srings "ab" and "cd".
Note that this means that he cannot tear a string of odd length. Since he is lazy he wants to minimize the number of tears needed to get a string which he likes. Help him find the minimum number.

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

The first line of the input contains an integer T denoting the number of test cases.
Following this, there are T lines, each consisting of a string S.

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

For each test case, output a single line containing a single integer, the minimum number of tears he must make to get a string which he likes.
If he cannot do so, output -1.

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

$|S|  ≤ 1,00,000$
$S contains only lowercase letters$
$the sum of |S| over all the test cases is less than or equal to 5,00,000$

----- Sample Input 1 ------ 
2
aacabbaa
aab
----- Sample Output 1 ------ 
2
-1
----- explanation 1 ------ 
Testcase 1:
Chef first tears the string at the middle (aaca|bbaa). 
Now he picks the first substring (ie. "aaca") and cuts this at the middle(aa|ca).
He now has the substring "aa" which only contains 'a'. 2 tears were needed and this is the minimum possible.

Testcase 2:
The chef cannot tear the string as it has length 3. So he cannot make string that he likes.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
def snek(s, k):
	if len(set(s)) == 1:
		return k
	if len(s) == 1:
		return k
	if len(s) % 2 == 1:
		return float('inf')
	m = (0 + len(s) - 1) // 2
	return min(snek(s[:m + 1], k + 1), snek(s[m + 1:], k + 1))
t = int(input())
for i in range(t):
	k = 0
	s = input()
	if len(set(s)) == 1:
		print(0)
	elif len(s) % 2 == 1:
		print(-1)
	else:
		ans = snek(s, k)
		if ans == float('inf'):
			print(-1)
		else:
			print(ans)


def get_divided_string(s):
	n = len(s)
	return (s[:n // 2], s[n // 2:])
maxi = 10 ** 10

def solve(l, min_steps):
	n = len(l)
	if len(set(l)) == 1:
		return min_steps
	if n % 2 == 1:
		return maxi
	else:
		(x, y) = get_divided_string(l)
		a = solve(x, min_steps + 1)
		b = solve(y, min_steps + 1)
		return min(a, b)
for _ in range(int(input())):
	l = input()
	if len(l) == 1:
		print(0)
		continue
	ans = solve(l, 0)
	print(-1 if ans == maxi else ans)


from math import *

def check(s):
	if len(set(s)) == 1:
		return len(s)
	if len(s) % 2 == 1:
		return -1
	return 0

def f(s):
	l = len(s)
	if check(s) != 0:
		return check(s)
	return max(f(s[0:l // 2]), f(s[l // 2:]))
for _ in range(int(input())):
	s = input()
	ans = f(s)
	if ans == -1:
		print('-1')
	else:
		print(int(log(len(s), 2)) - int(log(ans, 2)))


def solve(str, l, r):
	if len(set(list(str[l:r + 1]))) == 1:
		return 0
	if (r - l + 1) % 2:
		return 100000
	mid = (l + r) // 2
	return min(100000, min(solve(str, l, mid), solve(str, mid + 1, r)) + 1)
for _ in range(int(input())):
	str = input()
	l = len(str)
	ans = solve(str, 0, l - 1)
	if ans == 100000:
		print(-1)
	else:
		print(ans)


def solve(s, l, r, n, cnt):
	if len(set(list(s[l:r + 1]))) == 1:
		return cnt
	elif (r - l + 1) % 2 == 1:
		return 1000000
	mid = (l + r) // 2
	a = solve(s, l, mid, n, cnt + 1)
	b = solve(s, mid + 1, r, n, cnt + 1)
	return min(a, b)
for _ in range(int(input())):
	s = input()
	n = len(s)
	x = solve(s, 0, n - 1, n, 0)
	if x == 1000000:
		print(-1)
	else:
		print(x)


T = int(input().strip())
for t in range(T):
	s = input().strip()
	l = len(s)
	n = l
	k = 0
	while n & 1 == 0:
		n //= 2
		k += 1
	temp = []
	for i in range(0, l, n):
		if len(set(s[i:i + n])) == 1:
			temp.append(s[i])
		else:
			temp.append(None)
	if any(temp):
		while k:
			temp = [temp[i] if temp[i] and temp[i] == temp[i + 1] else None for i in range(0, len(temp), 2)]
			if any(temp):
				k -= 1
			else:
				break
		print(k)
	else:
		print(-1)


def is_good(num):
	r = num[0]
	for i in range(len(num)):
		if r != num[i]:
			return False
	return True

def count_pal(S, cnt):
	if is_good(S):
		return cnt
	elif len(S) % 2 == 1:
		return -1
	else:
		r1 = count_pal(S[:len(S) // 2], cnt + 1)
		r2 = count_pal(S[len(S) // 2:], cnt + 1)
		mini = min(r1, r2)
		if mini == -1:
			return max(r1, r2)
		else:
			return min(r1, r2)
T = int(input())
for i in range(T):
	S = input()
	print(count_pal(S, 0))


from collections import Counter

def all_same(s):
	if len(Counter(s)) != 1:
		return False
	return True
for i in range(int(input())):
	s = input()
	if len(Counter(s)) == 1:
		print(0)
		continue
	if len(s) % 2 != 0:
		print(-1)
		continue
	count = 1
	queue = [s[:len(s) // 2], s[len(s) // 2:]]
	breakit = False
	while queue:
		for st in queue:
			if all_same(st):
				print(count)
				breakit = True
				break
		if breakit is True:
			break
		nq = []
		for st in queue:
			if len(st) % 2 == 0:
				nq.append(st[:len(st) // 2])
				nq.append(st[len(st) // 2:])
		queue = nq
		count += 1
	if breakit:
		continue
	print(-1)


def func(a, num):
	if len(set(a)) == 1:
		return num
	if len(a) % 2:
		return 100000000000.0
	return min(func(a[:len(a) // 2], num + 1), func(a[len(a) // 2:], num + 1))
t = int(input())
while t:
	t -= 1
	a = input()
	ans = func(a, 0)
	if ans == 100000000000.0:
		print(-1)
	else:
		print(ans)


def all_same(s, i, j):
	u = s[i]
	for it in range(i + 1, j + 1):
		if s[it] != u:
			return False
	return True

def div(s, i, j, d):
	if i > j:
		return None
	if all_same(s, i, j):
		return d
	if (j - i + 1) % 2 != 0:
		return None
	m = (i + j) // 2
	l = div(s, i, m, d + 1)
	r = div(s, m + 1, j, d + 1)
	if l == None and r == None:
		return None
	if l == None:
		return r
	if r == None:
		return l
	return min(l, r)
for t in range(int(input())):
	s = input()
	ans = div(s, 0, len(s) - 1, 0)
	if ans == None:
		print(-1)
	else:
		print(ans)