Two words are anagrams of one another if their letters can be rearranged to form the other word.  

Given a string, split it into two contiguous substrings of equal length.  Determine the minimum number of characters to change to make the two substrings into anagrams of one another.

Example 

$s=\textbf{abccde}$  

Break $\boldsymbol{\mathrm{~S~}}$ into two parts: 'abc' and 'cde'.  Note that all letters have been used, the substrings are contiguous and their lengths are equal.  Now you can change 'a' and 'b' in the first substring to 'd' and 'e' to have 'dec' and 'cde' which are anagrams.  Two changes were necessary.

Function Description

Complete the anagram function in the editor below.    

anagram has the following parameter(s):  

string s: a string  

Returns  

int: the minimum number of characters to change or -1. 

Input Format

The first line will contain an integer, $\textit{q}$, the number of test cases. 

Each test case will contain a string $\boldsymbol{\mathrm{~S~}}$.

Constraints

$1\leq q\leq100$ 

$1\leq|s|\leq10^4$  
$\boldsymbol{\mathrm{~S~}}$ consists only of characters in the range ascii[a-z].  

Sample Input
6
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

Sample Output
3
1
-1
2
0
1

Explanation

Test Case #01: We split $\boldsymbol{\mathrm{~S~}}$ into two strings $\mbox{S1}$='aaa' and $\mbox{S2}$='bbb'.  We have to replace all three characters from the first string with 'b' to make the strings anagrams. 

Test Case #02: You have to replace 'a' with 'b', which will  generate "bb". 

Test Case #03: It is not possible for two strings of unequal length to be anagrams of one another. 

Test Case #04: We have to replace both the characters of first string ("mn") to make it an anagram of the other one. 

Test Case #05: $\mbox{S1}$ and $\mbox{S2}$ are already anagrams of one another. 

Test Case #06: Here S1 = "xaxb" and S2 = "bbxx". You must replace 'a' from S1 with 'b' so that S1 = "xbxb".

Difficulty: EASY
Tags: String algorithms

Starter code:

Solutions:
T = int(input())
for i in range(0, T):
	al = input()
	l = len(al)
	if l % 2 == 0:
		half = int(l / 2)
		a = al[:half]
		b = al[half:]
		count = 0
		for c in a:
			if c in b:
				pos = b.find(c)
				b = b[:pos] + b[pos + 1:]
			else:
				count += 1
		print(count)
	else:
		print(-1)


testcase = int(input())
for i in range(testcase):
	count = 0
	string = input()
	if len(string) % 2 == 1:
		print(-1)
	else:
		firsthalf = list(string[0:int(len(string) / 2)])
		secondhalf = list(string[int(len(string) / 2):])
		for j in firsthalf:
			if j not in secondhalf:
				count += 1
			if j in secondhalf:
				secondhalf.remove(j)
		print(count)


from collections import Counter

def main():
	N = int(input())
	for i in range(N):
		line = input().strip()
		if len(line) % 2 != 0:
			print(-1)
			continue
		c = 0
		(a, b) = (line[:len(line) // 2], line[len(line) // 2:])
		aa = Counter(a)
		bb = Counter(b)
		for x in aa:
			t = bb.get(x, 0)
			if t:
				del bb[x]
			c += abs(aa[x] - t)
		for x in bb:
			c += abs(bb[x] - aa.get(x, 0))
		print(c // 2)
main()


for i in range(int(input())):
	s = input()
	l1 = l2 = 0
	if len(s) % 2 == 1:
		print(-1)
	else:
		a = s[0:len(s) // 2]
		b = s[len(s) // 2:]
		c = ''
		for i in set(a):
			if a.count(i) > b.count(i):
				l1 += a.count(i) - b.count(i)
			if a.count(i) > 0 and b.count(i) > 0:
				c += i * min(a.count(i), b.count(i))
		for i in set(b):
			l2 += b.count(i) - c.count(i)
		if l1 <= l2:
			print(l1)
		else:
			print(-1)


import string

def solve(a, b):
	sum = 0
	for c in string.ascii_lowercase:
		c_in_a = a.count(c)
		c_in_b = b.count(c)
		if c_in_a > c_in_b:
			sum += c_in_a - c_in_b
	return sum

def main():
	N = int(input())
	for i in range(N):
		s = input()
		l = len(s)
		if l % 2 != 0:
			print('-1')
		else:
			print(solve(s[:l // 2], s[l // 2:]))
main()


def freq_counts(word):
	freq = dict()
	for char in word:
		if char in freq:
			freq[char] += 1
		else:
			freq[char] = 1
	return freq
n = int(input())
for i in range(n):
	string = input().strip()
	len_string = len(string)
	if len_string % 2 == 1:
		print(-1)
		continue
	first = freq_counts(string[:len_string // 2])
	second = freq_counts(string[len_string // 2:])
	count = 0
	for char in first:
		if char in second:
			num = first[char] - second[char]
			if num > 0:
				count += num
		else:
			count += first[char]
	print(count)


def anagram_check(x):
	if len(x) % 2 == 1:
		return -1
	n = len(x) // 2
	s1 = x[:n]
	s2 = x[n:]
	ch_map = {}
	count = 0
	for i in s1:
		if i in ch_map:
			ch_map[i] += 1
		else:
			ch_map[i] = 1
	for i in s2:
		if i in ch_map and ch_map[i] > 0:
			ch_map[i] -= 1
		else:
			count += 1
	return count
n = int(input())
for i in range(n):
	x = input()
	y = anagram_check(x)
	print(y)


import sys

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

def getLetterCounts(string):
	counts = {}
	for c in string:
		if c in counts:
			counts[c] += 1
		else:
			counts[c] = 1
	return counts
tests = int(getLine())
for testNr in range(tests):
	line = getLine()
	if len(line) % 2:
		print(-1)
		continue
	(A, B) = (line[:len(line) // 2], line[len(line) // 2:])
	(cA, cB) = map(getLetterCounts, [A, B])
	changes = 0
	for (kB, vB) in cB.items():
		if kB not in cA:
			changes += vB
		else:
			vA = cA[kB]
			if vA < vB:
				changes += vB - vA
	print(changes)


def get_test_input():
	num_of_inputs = int(input())
	tests = []
	for i in range(num_of_inputs):
		tests.append(input())
	return tests

def get_output(testCase):
	if len(testCase) % 2 != 0:
		return -1
	half = len(testCase) // 2
	(a, b) = (testCase[:half], testCase[half:])
	maps = {}
	for i in b:
		if i not in maps:
			maps[i] = 1
		else:
			maps[i] += 1
	for i in a:
		if i in maps and maps[i] > 0:
			half -= 1
			maps[i] -= 1
	return half
for testCase in get_test_input():
	print(get_output(testCase))


import collections, sys
T = int(sys.stdin.readline())
for _ in range(T):
	s = sys.stdin.readline().strip()
	if len(s) % 2:
		print(-1)
	else:
		(s1, s2) = (s[:len(s) // 2], s[len(s) // 2:])
		c2 = collections.Counter(s2)
		replacements = len(s1)
		for c in s1:
			if c in c2 and c2[c] > 0:
				replacements -= 1
				c2[c] -= 1
		print(replacements)


def func(st):
	if len(st) % 2:
		return -1
	else:
		d = {}
		for i in range(len(st) // 2):
			d[st[i]] = d.get(st[i], 0) + 1
		for i in range(len(st) // 2, len(st)):
			d[st[i]] = d.get(st[i], 0) - 1
		rt = 0
		for k in d:
			rt += abs(d[k])
		return rt // 2
t = int(input())
for i in range(t):
	print(func(input()))


import sys
T = int(sys.stdin.readline())

def find_freqs(string):
	freqs = {}
	for s in string:
		freqs[s] = freqs.get(s, 0) + 1
	return freqs

def find_diff(string):
	strlen = len(string)
	left = string[0:strlen // 2]
	right = string[strlen // 2:]
	leftf = find_freqs(left)
	rightf = find_freqs(right)
	counter = 0
	for (k, v) in rightf.items():
		f = leftf.get(k, 0)
		if v > f:
			counter += v - f
	return counter
for line in sys.stdin:
	line = line.replace('\n', '')
	if len(line) % 2 != 0:
		print(-1)
	else:
		print(find_diff(line))


def findMin(x):
	l = len(x)
	if l % 2 == 0:
		s1 = x[:l // 2]
		s2 = x[l // 2:]
		s1l = list(s1)
		s2l = list(s2)
		s1l.sort()
		s2l.sort()
		d1 = dict()
		d2 = dict()
		for i in range(0, l // 2):
			try:
				d1[s1l[i]] += 1
			except KeyError:
				d1[s1l[i]] = 1
			try:
				d2[s2l[i]] += 1
			except KeyError:
				d2[s2l[i]] = 1
		c = 0
		for e in d2:
			if e in d1:
				c += abs(d2[e] - d1[e])
				d1[e] = d2[e]
			if e not in d1:
				c += d2[e]
				d1[e] = d2[e]
		for e in d1:
			if e not in d2:
				c += d1[e]
				d1[e] = -99
		return c // 2
	else:
		return -1
t = int(input())
for i in range(0, t):
	print(findMin(input()))


def update(s, side):
	for l in s:
		freq[l] = freq.get(l, 0) + side
for t in range(int(input())):
	freq = {}
	l = input()
	if len(l) % 2:
		print(-1)
	else:
		(s1, s2) = (l[:len(l) // 2], l[len(l) // 2:])
		update(s1, 1)
		update(s2, -1)
		print(sum(map(abs, freq.values())) // 2)


T = int(input())
for t in range(0, T):
	s = input()
	if len(s) % 2 == 1:
		print(-1)
		continue
	Diff = {}
	for i in s[:len(s) // 2]:
		Diff[i] = Diff.get(i, 0) + 1
	for i in s[len(s) // 2:]:
		Diff[i] = Diff.get(i, 0) - 1
	count = 0
	for d in Diff:
		if Diff[d] > 0:
			count += Diff[d]
		else:
			count -= Diff[d]
	print(count // 2)


import string
t = int(input())
for numtest in range(t):
	word = list(input())
	if len(word) % 2 == 1:
		print(-1)
	else:
		wordL = int(len(word) / 2)
		w1 = word[0:wordL]
		w2 = word[wordL:2 * wordL]
		freq1 = {c: 0 for c in string.ascii_lowercase}
		freq2 = {c: 0 for c in string.ascii_lowercase}
		for c in w1:
			freq1[c] += 1
		for c in w2:
			freq2[c] += 1
		diffs = [abs(freq1[ch] - freq2[ch]) for ch in string.ascii_lowercase]
		if wordL > 0:
			print(int(sum(diffs) / 2))
		else:
			print(-1)


n = int(input())
for i in range(0, n):
	str = input()
	if len(str) % 2 > 0:
		print(-1)
		continue
	str1 = str[:len(str) // 2]
	str2 = str[len(str) // 2:]
	d = {}
	for c in str1:
		if not c in d:
			d[c] = 0
		d[c] += 1
	count = 0
	for c in str2:
		if c in d and d[c] > 0:
			d[c] -= 1
		else:
			count += 1
	print(count)


def anagram(first, second):
	second = list(second)
	diff = 0
	for i in range(len(first)):
		if first[i] in second:
			second.remove(first[i])
		else:
			diff += 1
	return diff

def main():
	T = int(input())
	for i in range(T):
		word = input().rstrip()
		n = len(word)
		if n % 2 != 0:
			print('-1')
		else:
			half = int(n / 2)
			first = word[:half]
			second = word[half:]
			print(anagram(first, second))
main()


def getLens(s):
	leng = len(s)
	return (leng // 2, leng % 2)

def getNum(s, length):
	str1 = list(s[:length])
	str2 = s[length:]
	for i in str2:
		try:
			str1.remove(i)
		except:
			pass
	return len(str1)
x = int(input())
for i in range(x):
	s = input()
	tool = getLens(s)
	if tool[1] == 0:
		print(getNum(s, tool[0]))
	else:
		print(-1)


def calcNumChangesToAnagram(string):
	if len(string) % 2 != 0:
		return -1
	str1 = list(string[:int(len(string) / 2)])
	str2 = list(string[int(len(string) / 2):])
	calc = 0
	for i in range(0, len(str1)):
		if str1[i] in str2:
			str2.remove(str1[i])
	return len(str2)

def processInput():
	m = int(input())
	for i in range(0, m):
		print(calcNumChangesToAnagram(input().strip()))
processInput()


n = int(input())
for i in range(n):
	str = input()
	if len(str) % 2:
		print(-1)
	else:
		cnt = 0
		half = int(len(str) / 2)
		str1 = sorted(str[:half])
		str2 = sorted(str[half:])
		for c in str1:
			if c not in str2:
				cnt += 1
			else:
				str2.remove(c)
		print(cnt)


t = int(input())
for i in range(t):
	text = input()
	if len(text) % 2 == 1:
		print(-1)
	else:
		lf = [0] * 26
		rf = [0] * 26
		for i in range(0, len(text) // 2):
			lf[ord(text[i]) - 97] += 1
		for i in range(len(text) // 2, len(text)):
			rf[ord(text[i]) - 97] += 1
		print(sum([abs(x1 - x2) for (x1, x2) in zip(lf, rf)]) // 2)


import sys
n = int(sys.stdin.readline())
for test in range(n):
	line = sys.stdin.readline()
	strlen = len(line) - 1
	if strlen % 2 != 0:
		sys.stdout.write('{}\n'.format(-1))
		continue
	a = len(line) // 2
	chars = [0 for i in range(26)]
	for i in range(a):
		c = ord(line[i]) - 97
		chars[c] = chars[c] + 1
	diff = 0
	for i in range(a):
		c = ord(line[a + i]) - 97
		if chars[c] == 0:
			diff = diff + 1
		else:
			chars[c] = chars[c] - 1
	sys.stdout.write('{}\n'.format(diff))


for n in range(int(input())):
	s = input()
	if len(s) % 2 == 1:
		print(-1)
	else:
		a = list(s[:int(len(s) / 2)])
		b = list(s[int(len(s) / 2):])
		for c in b:
			if c in a:
				a.remove(c)
		print(len(a))


def anagram(input_string):
	if len(input_string) % 2 != 0:
		return -1
	changes_count = 0
	first_word = input_string[:len(input_string) // 2]
	second_word = input_string[len(input_string) // 2:]
	for char in first_word:
		index = second_word.find(char)
		if index == -1:
			changes_count += 1
		else:
			second_word = second_word.replace(char, '', 1)
	return changes_count
num_lines = int(input())
for _ in range(num_lines):
	print(str(anagram(input())))


def shifts_required(input_str):
	shifts = 0
	if len(input_str) % 2:
		return -1
	(a, b) = (input_str[:len(input_str) // 2], input_str[len(input_str) // 2:])
	dict = {}
	dicta = {}
	for i in b:
		if i in dict.keys():
			dict[i] += 1
		else:
			dict[i] = 1
			dicta[i] = 0
	for i in a:
		if i in dicta.keys():
			dicta[i] += 1
		else:
			dicta[i] = 1
	for i in dict.keys():
		if dict[i] > dicta[i]:
			shifts += dict[i] - dicta[i]
	return shifts
t = int(input())
for _ in range(t):
	print(shifts_required(input()))


for q in range(int(input())):
	a = input()
	if len(a) % 2 == 0:
		st1 = a[:len(a) // 2]
		st2 = a[len(a) // 2:]
		count1 = [0 for i in range(26)]
		for i in st1:
			count1[ord(i) - 97] += 1
		count2 = [0 for i in range(26)]
		for i in st2:
			count2[ord(i) - 97] += 1
		r = 0
		for i in range(26):
			if count1[i] > count2[i]:
				r += count1[i] - count2[i]
		print(r)
	else:
		print(-1)


def changeCount(text):
	res = 0
	if len(text) % 2 != 0:
		return -1
	a = text[0:len(text) // 2]
	b = text[len(text) // 2:]
	for c in a:
		if c in b:
			b = b.replace(c, '', 1)
		else:
			res += 1
	return (res + len(b)) // 2
for i in range(int(input())):
	print(changeCount(input().strip()))


lines = input()
for line in range(int(lines)):
	line = input()
	if len(line) % 2 == 1:
		print(-1)
	else:
		a = line[:len(line) // 2]
		b = line[len(line) // 2:]
		count = 0
		for i in range(len(line) // 2):
			if a[i] not in b:
				count += 1
			else:
				b = b.replace(a[i], ' ', 1)
		print(count)


def difference(string):
	if len(string) % 2 != 0:
		print(-1)
		return
	string1 = string[:int(len(string) / 2)]
	string2 = string[int(len(string) / 2):]
	set1 = set(string1)
	set2 = set(string2)
	dict1 = {}
	dict2 = {}
	changes = 0
	for i in set1:
		dict1[i] = string1.count(i)
	for i in set2:
		dict2[i] = string2.count(i)
	for i in dict1:
		try:
			changes += abs(dict1[i] - dict2[i])
			dict2.pop(i)
		except KeyError:
			changes += dict1[i]
	for i in dict2:
		changes += dict2[i]
	print(int(changes / 2))
T = int(input())
for i in range(T):
	x = input()
	difference(x)


t = int(input())
for _ in range(t):
	s = input().strip()
	l = len(s)
	l = int(l)
	if l % 2 == 1:
		print('-1')
	else:
		l = l // 2
		x = s[:l]
		y = s[l:]
		x = sorted(x)
		y = sorted(y)
		c = 0
		cx = [0 for i in range(26)]
		cy = [0 for i in range(26)]
		for i in range(l):
			cx[ord(x[i]) - 97] += 1
			cy[ord(y[i]) - 97] += 1
		for i in range(26):
			c += abs(cy[i] - cx[i])
		print(c // 2)


import collections
T = int(input())

def anagram_diff(s):
	result = 0
	L = len(s)
	if L % 2 == 1:
		return -1
	letters = collections.defaultdict(int)
	for i in range((L + 1) // 2):
		letters[s[i]] += 1
	for i in range((L + 1) // 2, L):
		letters[s[i]] -= 1
	for (k, v) in letters.items():
		if v > 0:
			result += v
	return result
for tc in range(T):
	i = input().strip()
	r = anagram_diff(i)
	print(r)


T = int(input())
for i in range(T):
	s = input()
	l = len(s)
	if l & 1:
		print(-1)
	else:
		hl = l // 2
		sa = {}
		for c in s[:hl]:
			if c in sa:
				sa[c] += 1
			else:
				sa[c] = 1
		n = 0
		for c in s[hl:]:
			if c in sa and sa[c] > 0:
				sa[c] -= 1
			else:
				n += 1
		print(n)


numtests = int(input())
tests = []
for i in range(numtests):
	tests.append(input())
for i in range(numtests):
	mystring = tests[i]
	if len(mystring) % 2 == 0:
		count = 0
		string1 = list(mystring[0:len(mystring) // 2])
		string2 = list(mystring[len(mystring) // 2:])
		for el in string1:
			if el in string2:
				string2.remove(el)
			else:
				count = count + 1
		print(count)
	else:
		print('-1')


import sys
indices = {c: i for (i, c) in enumerate('abcdefghijklmnopqrstuvwxyz')}
T = int(sys.stdin.readline())
for case in range(T):
	string = sys.stdin.readline().rstrip('\n')
	length = len(string)
	if length % 2 == 1:
		print(-1)
	else:
		string1 = string[:length // 2]
		list1 = [0] * 26
		for c in string1:
			list1[indices[c]] += 1
		string2 = string[length // 2:]
		list2 = [0] * 26
		for c in string2:
			list2[indices[c]] += 1
		print(sum([abs(a - b) for (a, b) in zip(list1, list2)]) // 2)


import sys
from collections import Counter

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		string = sys.stdin.readline().strip()
		print(anagram(string))

def anagram(string):
	if len(string) % 2 == 1:
		return -1
	a = Counter(string[:len(string) // 2])
	b = Counter(string[len(string) // 2:])
	differences = 0
	for letter in a:
		if letter in b:
			if a[letter] >= b[letter]:
				differences += a[letter] - b[letter]
		else:
			differences += a[letter]
	return differences
main()


import sys
T = sys.stdin.readline()

def isAnagram(s1, s2):
	cnt = 0
	vett = [0] * 26
	for i in range(len(s2)):
		vett[ord(s2[i]) - ord('a')] += 1
	for i in range(len(s1)):
		if vett[ord(s1[i]) - ord('a')] > 0:
			vett[ord(s1[i]) - ord('a')] -= 1
	for e in vett:
		if e > 0:
			cnt += e
	return cnt
for line in sys.stdin:
	if line[-1] == '\n':
		line = line[:-1]
	if len(line) % 2 == 1:
		print(-1)
	else:
		s1 = line[:len(line) // 2]
		s2 = line[len(line) // 2:]
		print(isAnagram(s1, s2))


pos = {}
i = 0
for ch in 'abcdefghijklmnopqrstuvwxyz':
	pos[ch] = i
	i += 1

def parsestring(s):
	r = [0] * 26
	for ch in s:
		r[pos[ch]] += 1
	return r
T = int(input())
for Ti in range(T):
	c = input()
	if len(c) % 2 == 1:
		print(-1)
		continue
	l = len(c) // 2
	r1 = parsestring(c[:l])
	r2 = parsestring(c[l:])
	count = 0
	for i in range(26):
		cur = r2[i] - r1[i]
		if cur > 0:
			count += cur
	print(count)


t = int(input())
for i in range(t):
	s = input().strip()
	if len(s) % 2 != 0:
		print(-1)
		continue
	a = s[:len(s) // 2]
	b = s[len(s) // 2:]
	cs = [0] * 256
	for c in a:
		i = ord(c)
		cs[i] += 1
	for c in b:
		i = ord(c)
		cs[i] -= 1
	for (i, e) in enumerate(cs):
		cs[i] = abs(e)
	print(sum(cs) // 2)


N = int(input())
for i in range(N):
	fullStr = input()
	l = len(fullStr)
	if l % 2:
		print(-1)
		continue
	else:
		str1 = fullStr[:l // 2]
		str2 = fullStr[l // 2:]
		str2List = list(str2)
		result = 0
		for i in range(len(str1)):
			if str1[i] in str2List:
				str2List.remove(str1[i])
			else:
				result += 1
		print(result)


def char_dict(string):
	ret_dict = {}
	for ch in string:
		if ch in ret_dict:
			ret_dict[ch] += 1
		else:
			ret_dict[ch] = 1
	return ret_dict
num_test = int(input().strip())
for i in range(num_test):
	string = input().strip()
	if len(string) % 2 != 0:
		print(-1)
		continue
	mid_index = int(len(string) / 2)
	str1 = string[:mid_index]
	str2 = string[mid_index:]
	dict1 = char_dict(str1)
	dict2 = char_dict(str2)
	for key in dict1:
		if key in dict2:
			dict1[key] -= dict2[key]
	count = 0
	for key in dict1:
		if dict1[key] > 0:
			count += dict1[key]
	print(count)


import fileinput

def changesToMakeAnagram(line):
	length = len(line)
	if length % 2:
		return -1
	line1 = line[:int(length / 2)]
	line2 = line[int(length / 2):]
	changes = 0
	while len(line1) > 0:
		char = line1[0]
		count1 = line1.count(char)
		count2 = line2.count(char)
		if count1 > count2:
			changes += count1 - count2
		line1 = line1.replace(char, '')
	return changes
for line in fileinput.input():
	if fileinput.lineno() != 1:
		print(changesToMakeAnagram(line.strip()))


T = int(input())
for t in range(T):
	s = input().strip()
	if len(s) % 2 == 1:
		print(-1)
	else:
		mid = int(len(s) / 2)
		a = []
		b = []
		for i in range(26):
			a.append(0)
			b.append(0)
		for c in s[:mid]:
			a[ord(c) - ord('a')] += 1
		for c in s[mid:]:
			b[ord(c) - ord('a')] += 1
		print(sum([max(0, a[i] - b[i]) for i in range(26)]))


x = int(input().strip())
for i in range(x):
	s = input().strip()
	if len(s) % 2 != 0:
		print('-1')
	else:
		a = s[0:len(s) // 2]
		b = s[len(s) // 2:]
		for x in a:
			if x in b:
				b = b.replace(x, '', 1)
		print(len(b))


T = int(input().strip())
for t in range(T):
	ab = input().strip()
	if len(ab) % 2 == 1:
		print(-1)
	else:
		n = len(ab) // 2
		(a, b) = (ab[n:], ab[:n])
		d = 0
		for x in set(ab):
			cxd = a.count(x) - b.count(x)
			if cxd > 0:
				d += cxd
		print(d)


def abs(x):
	return -x if x < 0 else x
T = int(input())
for t in range(T):
	s = str(input())
	if len(s) % 2 == 1:
		print(-1)
		continue
	a = [i for i in s[0:len(s) // 2]]
	b = [j for j in s[len(s) // 2:len(s)]]
	count = dict.fromkeys(set(a).union(set(b)), 0)
	for (i, j) in zip(a, b):
		count[i] += 1
		count[j] -= 1
	ans = 0
	for (key, value) in count.items():
		ans += abs(value)
	print(ans // 2)


import sys
from collections import defaultdict
from string import ascii_letters

def freqdiff(words):
	s1 = words[:len(words) // 2]
	s2 = words[len(words) // 2:]
	if len(s1) != len(s2):
		result = -1
	else:
		freq1 = {k: 0 for k in ascii_letters}
		freq2 = {k: 0 for k in ascii_letters}
		for s in s1:
			freq1[s] += 1
		for s in s2:
			freq2[s] += 1
		freqdiff = {k: abs(freq1[k] - freq2[k]) for k in freq1.keys()}
		result = sum(freqdiff.values())
		assert result % 2 == 0
		result = result // 2
	return result
T = int(sys.stdin.readline().strip())
while T > 0:
	words = sys.stdin.readline().strip()
	print(freqdiff(words))
	T -= 1


num_testcase = int(input())
for i_testcase in range(num_testcase):
	concatenation = input()
	if len(concatenation) % 2 != 0:
		print(-1)
		continue
	string1 = concatenation[:int(len(concatenation) / 2)]
	string2 = concatenation[int(len(concatenation) / 2):]
	str_list2 = list(string2)
	for char in string1:
		if char in str_list2:
			str_list2.remove(char)
	print(len(str_list2))


from collections import defaultdict
for _ in range(int(input())):
	s = input()
	n = len(s)
	if n % 2 == 1:
		print(-1)
	else:
		d = defaultdict(int)
		for c in s[:int(n / 2)]:
			d[c] += 1
		for c in s[int(n / 2):]:
			d[c] -= 1
		print(int(sum([abs(x) for x in d.values()]) / 2))


import sys
inp = iter(sys.stdin)

def read_line():
	return next(inp)
T = int(read_line())

def resolve(text):
	first = text[:text.__len__() // 2]
	second = text[text.__len__() // 2:]
	count = 0
	for char in first:
		if char not in second:
			count += 1
		else:
			second = second.replace(char, '', 1)
	return count
for _ in range(T):
	text = read_line().strip()
	if text.__len__() % 2 == 1:
		print('-1')
	else:
		print(resolve(text))


import collections
cases = int(input())
for i in range(0, cases):
	string = input()
	if len(string) % 2 != 0:
		print('-1')
	else:
		l = len(string)
		length = int(l / 2)
		one = string[0:length]
		two = string[length:l]
		one = sorted(one)
		two = sorted(two)
		d1 = {}
		d2 = {}
		for i in range(0, len(one)):
			d1[one[i]] = 0
			d2[two[i]] = 0
		for i in range(0, len(one)):
			d1[one[i]] += 1
			d2[two[i]] += 1
		count = 0
		for key in d2:
			if key in d1.keys():
				if d1[key] < d2[key]:
					count += d2[key] - d1[key]
			else:
				count += d2[key]
		print(count)


T = int(input())
for t in range(T):
	anagram = input()
	wordsLen = int(len(anagram))
	if wordsLen % 2 == 1:
		print(-1)
		continue
	firstword = anagram[:int(wordsLen / 2)]
	secondword = anagram[int(wordsLen / 2):]
	lettersCount = dict()
	for c in secondword:
		if c in lettersCount:
			lettersCount[c] += 1
		else:
			lettersCount[c] = 1
	for c in firstword:
		if c in lettersCount:
			lettersCount[c] -= 1
			if lettersCount[c] == 0:
				del lettersCount[c]
	missing = sum(lettersCount.values())
	print(missing)


T = int(input())
for i in range(T):
	line = input().rstrip()
	if len(line) % 2 != 0:
		print(-1)
	else:
		half = int(len(line) / 2)
		a = line[:half]
		b = line[half:]
		chars = {}
		for c in a:
			if not c in chars:
				chars[c] = 1
			else:
				chars[c] += 1
		for c in b:
			if not c in chars:
				chars[c] = -1
			else:
				chars[c] -= 1
		print(int(sum([abs(x) for x in chars.values()]) / 2))


T = int(input())
for i in range(T):
	line = input()
	if len(line) % 2 != 0:
		print(-1)
		continue
	dict_a = dict()
	for c in line[:len(line) // 2]:
		dict_a[c] = dict_a.get(c, 0) + 1
	others = 0
	for c in line[len(line) // 2:]:
		if dict_a.get(c, 0):
			dict_a[c] -= 1
		else:
			others += 1
	print(others)


t = int(input())
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def histogram(w):
	h = dict(((l, 0) for l in alphabet))
	for c in w:
		h[c] += 1
	return h
for _ in range(t):
	w = input()
	lw = len(w)
	if lw % 2 == 1:
		print(-1)
		continue
	(a, b) = (w[:lw // 2], w[lw // 2:])
	(ha, hb) = (histogram(a), histogram(b))
	r = sum((hb[l] - min(hb[l], ha[l]) for l in alphabet))
	print(r)


from math import floor

def anagram(a, b):
	if len(a) != len(b):
		return -1
	a_l = list(a)
	for x in b:
		try:
			a_l.remove(x)
		except ValueError:
			pass
	return len(a_l)
T = int(input())
for _ in range(T):
	line = input().rstrip()
	delim = floor(len(line) / 2)
	(a, b) = (line[:delim], line[delim:])
	print(anagram(a, b))


T = int(input())

def anagramHash(string):
	d = {}
	for alpha in 'abcdefghijklmnopqrstuvwxyz':
		d[alpha] = 0
	for char in string:
		d[char] += 1
	return d
for _ in range(T):
	string = input()
	l = len(string)
	if l % 2 != 0:
		print(-1)
	else:
		a = string[:l // 2]
		b = string[l // 2:]
		aHash = anagramHash(a)
		bHash = anagramHash(b)
		diff = 0
		for key in aHash:
			diff += abs(aHash[key] - bHash[key])
		print(diff // 2)


from collections import Counter

def solve(num_list):
	str_len = len(num_list)
	if str_len % 2 == 1:
		return -1
	half_len = str_len // 2
	first = Counter(num_list[:half_len])
	second = Counter(num_list[half_len:])
	changes = half_len
	for v in range(26):
		changes -= min(first[v], second[v])
	return changes
t = int(input())
for i in range(t):
	num_list = [ord(v) - ord('a') for v in input()]
	print(solve(num_list))


def replacements(s):
	split = len(s) // 2
	(a, b) = (s[:split], s[split:])
	total = 0
	for letter in set(a):
		(aCount, bCount) = (a.count(letter), b.count(letter))
		if aCount > bCount:
			total += aCount - bCount
	return total
n = int(input())
cases = [input() for i in range(n)]
results = [replacements(case) if len(case) % 2 == 0 else -1 for case in cases]
print('\n'.join((str(res) for res in results)))


import math
num1 = input()
for tc in range(0, int(num1)):
	s = input()
	if len(s) % 2 == 1:
		print('-1')
	else:
		half = math.floor(len(s) / 2)
		s1 = s[0:half]
		s2 = s[half:]
		total = ord('z') + 1 - ord('a')
		arr = [0] * total
		in_common = 0
		for ch1 in s2:
			index = ord(ch1) - ord('a')
			arr[index] += 1
		for ch2 in s1:
			index = ord(ch2) - ord('a')
			if arr[index] > 0:
				in_common += 1
			arr[index] -= 1
		print(str(half - in_common))


testcases = int(input())

def isana(test):
	if len(test) % 2 == 1:
		return -1
	first = test[:len(test) // 2]
	second = test[len(test) // 2:]
	for character in range(len(first)):
		if first[character] in second:
			second = second.replace(first[character], '', 1)
	return len(second)
for t in range(testcases):
	test = input()
	print(isana(test))


def anagramChanges(string):
	if len(string) % 2 == 1:
		return -1
	count = 0
	alreadyCounted = ''
	stringA = string[:len(string) // 2]
	stringB = string[len(string) // 2:]
	for letter in stringB:
		if letter not in alreadyCounted:
			occurencesB = stringB.count(letter)
			occurencesA = stringA.count(letter)
			if occurencesB > occurencesA:
				count += occurencesB - occurencesA
			alreadyCounted += letter
	return count
t = int(input())
assert 1 <= t <= 100
for i in range(t):
	string = input().strip()
	assert 1 <= len(string) <= 10000
	print(anagramChanges(string))


from collections import Counter
n = int(input())
for i in range(n):
	s = input()
	if len(s) % 2 != 0:
		print(-1)
	else:
		a = Counter(s[:len(s) // 2])
		b = Counter(s[len(s) // 2:])
		c = a - b
		d = b - a
		if sum(c.values()) != sum(d.values()):
			print(-1)
		else:
			print(sum(c.values()))


def anagramer(tests):
	for i in range(tests):
		string = input()
		length = len(string)
		if length % 2 == 1:
			print(-1)
		elif length % 2 == 0:
			halfway = int(length / 2)
			(string_a, string_b) = (string[:halfway], string[halfway:])
			count = 0
			for letter in 'abcdefghijklmnopqrstuvwxyz':
				count += abs(string_a.count(letter) - string_b.count(letter))
			print(count // 2)
anagramer(int(input()))


for i in range(int(input())):
	s = input()
	if len(s) % 2:
		print(-1)
	else:
		(s1, s2) = (s[:len(s) // 2], s[len(s) // 2:])
		c = 0
		for e in s1:
			if e in s2:
				s2 = s2.replace(e, '', 1)
			else:
				c += 1
		print(c)


t = int(input())
for _ in range(t):
	line = str(input())
	if len(line) % 2 == 1:
		print(-1)
		continue
	mid = len(line) // 2
	a = line[:mid]
	b = line[mid:]
	data = {}
	for i in range(mid):
		data[a[i]] = data[a[i]] + 1 if a[i] in data else 1
	count = 0
	for i in range(mid):
		if not b[i] in data:
			count += 1
		else:
			data[b[i]] -= 1
			if data[b[i]] == 0:
				del data[b[i]]
	print(count)


from collections import Counter

def odd(n):
	return bool(n % 2)

def dist_to_anagram(s):
	length = len(s)
	if odd(length):
		return -1
	a = s[:length // 2]
	b = Counter(s[length // 2:])
	count = 0
	for c in a:
		if b[c] > 0:
			b[c] -= 1
		else:
			count += 1
	return count
t = int(input())
strings = (input() for i in range(t))
for s in strings:
	print(dist_to_anagram(s))


def anagram_changes(a, b):
	differences = 0
	for char in a:
		if char in b:
			b = b.replace(char, '', 1)
		else:
			differences += 1
	return differences
for case in range(int(input())):
	string = input()
	if not len(string) % 2:
		(a, b) = (string[:len(string) // 2], string[len(string) // 2:])
		print(anagram_changes(a, b))
	else:
		print(-1)


for _ in range(int(input())):
	s = input()
	if len(s) % 2 == 1:
		print('-1')
	else:
		a = list(s[:len(s) // 2])
		b = list(s[len(s) // 2:])
		res = 0
		for item in a:
			if item in b:
				b.remove(item)
			else:
				res += 1
		print(res)


import sys
for x in range(0, int(sys.stdin.readline())):
	s = sys.stdin.readline().rstrip()
	if len(s) % 2 != 0:
		print(-1)
	else:
		(a, b) = (s[:int(len(s) / 2)], s[int(len(s) / 2):])
		for c in a:
			j = b.find(c)
			if j > -1:
				b = b[:j] + b[j + 1:]
		print(len(b))


from collections import defaultdict
n = int(input())
for _ in range(n):
	s = input()
	if len(s) % 2 == 0:
		count = defaultdict(int)
		for c in s[:len(s) // 2]:
			count[c] += 1
		for c in s[len(s) // 2:]:
			count[c] -= 1
		diff = 0
		for v in count.values():
			if v > 0:
				diff += v
		print(diff)
	else:
		print(-1)


import string
c = int(input())
for i in range(c):
	w = list(input())
	if len(w) % 2 == 1:
		print(-1)
		continue
	h = len(w) // 2
	w1 = w[:h]
	w2 = w[h:]
	h1 = {}
	h2 = {}
	for i in range(h):
		h1[w1[i]] = h1.get(w1[i], 0) + 1
		h2[w2[i]] = h2.get(w2[i], 0) + 1
	abc = list(string.ascii_lowercase)
	count = 0
	for l in abc:
		c1 = h1.get(l, 0)
		c2 = h2.get(l, 0)
		count += abs(c2 - c1)
	print(count // 2)


t = int(input())
for _ in range(t):
	s = input()
	if len(s) % 2 != 0:
		print(-1)
	else:
		a = list(s[:len(s) // 2])
		b = list(s[len(s) // 2:])
		ret = 0
		for i in a:
			if i in b:
				b.remove(i)
			else:
				ret += 1
		print(ret)


def anagram(string):
	length = len(string)
	if length % 2 == 1:
		return -1
	else:
		str1 = string[0:int(length / 2)]
		str2 = string[int(length / 2):]
	char1 = [x for x in str1]
	char2 = [x for x in str2]
	for element in char1[:]:
		if element in char2:
			char1.remove(element)
			char2.remove(element)
	return len(char1)
tcs = int(input())
for tc in range(tcs):
	string = input()
	print(anagram(string))


T = int(input())
for z in range(T):
	a_string = input()
	if len(a_string) % 2 == 1:
		print(-1)
	else:
		half = int(len(a_string) / 2)
		first = a_string[:half]
		second = a_string[half:]
		letters = {}
		for i in first:
			if i in letters:
				letters[i] += 1
			else:
				letters[i] = 1
		to_change = 0
		for j in second:
			if j in letters:
				if letters[j] > 0:
					letters[j] -= 1
				else:
					to_change += 1
			else:
				to_change += 1
		print(to_change)


def answer(string):
	l = len(string)
	if l % 2:
		return -1
	a = string[:l // 2]
	b = string[l // 2:]
	A = {aa: a.count(aa) for aa in a}
	B = {bb: b.count(bb) for bb in b}
	count = 0
	for key in B.keys():
		if key in A:
			if B[key] - A[key] > 0:
				count += B[key] - A[key]
		else:
			count += B[key]
	return count
n = int(input())
for t in range(n):
	string = input()
	print(answer(string))


N = int(input())
for i in range(N):
	s = str(input())
	if len(s) % 2 != 0:
		print('-1')
		continue
	(a, b) = (s[0:len(s) // 2], s[len(s) // 2:])
	D = dict()
	for c in a:
		try:
			D[c] += 1
		except:
			D[c] = 1
	n = 0
	for c in b:
		try:
			D[c] -= 1
			if D[c] < 0:
				n += 1
		except:
			n += 1
	print(n)


__author__ = 'danielbaeck'
t = int(input())
for i in range(t):
	text = input()
	if len(text) % 2 != 0:
		print('-1')
		continue
	text = list(text)
	t1 = text[:int(len(text) / 2)]
	t2 = text[int(len(text) / 2):]
	for a in t1[:]:
		if a in t2:
			t2.remove(a)
			t1.remove(a)
	print(len(t1))


import sys

def score(word):
	if len(word) & 1:
		return -1
	mid = int(len(word) / 2)
	a = word[0:mid]
	b = list(word[mid:])
	num = 0
	for i in range(len(a)):
		try:
			b.remove(a[i])
		except ValueError:
			num += 1
	return num
num = int(sys.stdin.readline())
for i in range(num):
	s = sys.stdin.readline().strip()
	print(score(s))


cases = int(input())
for case in range(cases):
	s = input()
	if len(s) % 2 == 1:
		print(-1)
	else:
		(l, r) = map(list, [s[:len(s) // 2], s[len(s) // 2:]])
		count = 0
		for x in l:
			if x in r:
				r.pop(r.index(x))
			else:
				count += 1
		print(count)


n = int(input())
for i in range(n):
	str = input()
	out = 0
	if len(str) % 2 != 0:
		print(-1)
		continue
	mid = int(len(str) / 2)
	myDict = dict()
	for j in range(mid):
		if str[j] in myDict:
			myDict[str[j]] += 1
		else:
			myDict[str[j]] = 1
	for j in range(mid, len(str)):
		if myDict.get(str[j]):
			myDict[str[j]] -= 1
		else:
			out += 1
	print(out)


def min_changes_for_anagram(ab_string):
	if len(ab_string) % 2 != 0:
		return -1
	mid = int(len(ab_string) / 2)
	a_str = ab_string[0:mid]
	b_str = ab_string[mid:]
	char_dict = {}
	for c in a_str:
		if c in char_dict:
			char_dict[c][0] += 1
		else:
			char_dict[c] = [1, 0]
	for c in b_str:
		if c in char_dict:
			char_dict[c][1] += 1
		else:
			char_dict[c] = [0, 1]
	diffs = 0
	for c in char_dict:
		diffs += abs(char_dict[c][0] - char_dict[c][1])
	return int(diffs / 2)
num_tests = int(input().strip())
ab_strings = []
for idx in range(0, num_tests):
	ab_string = input().strip()
	ab_strings.append(ab_string)
for ab_string in ab_strings:
	min_change = min_changes_for_anagram(ab_string)
	print(min_change)


import collections
T = int(input())
for _ in range(T):
	s = input()
	if len(s) % 2 == 1:
		print(-1)
		continue
	halfway = len(s) // 2
	c1 = collections.Counter(s[:halfway])
	c2 = collections.Counter(s[halfway:])
	print(len(list((c1 - c2).elements())))


testCases = int(input())
for x in range(0, testCases):
	string = input()
	stringLength = len(string)
	charDict = {}
	even = True
	if stringLength % 2 != 0:
		print(-1)
		even = False
	a = string[0:stringLength // 2]
	for char in a:
		if char in charDict:
			charDict[char] += 1
		else:
			charDict[char] = 1
	b = string[stringLength // 2:stringLength]
	for char in b:
		if char in charDict:
			charDict[char] -= 1
	if even:
		value = sum([x for x in charDict.values() if x > 0])
		print(value)


import fileinput

def getFreq(xs):
	BASE = ord('a')
	ret = {chr(BASE + i): 0 for i in range(26)}
	for x in xs:
		ret[x] += 1
	return ret
num = int(input())
for i in range(num):
	line = input()
	if len(line) % 2:
		print(-1)
	else:
		med = int(len(line) / 2)
		a_freq = getFreq(line[:med])
		b_freq = getFreq(line[med:])
		diff = 0
		for (alpha, count) in a_freq.items():
			diff += abs(count - b_freq[alpha])
		print(int(diff / 2))


import collections
t = int(input())
for _ in range(t):
	s = input()
	if len(s) % 2:
		print(-1)
		continue
	(a, b) = (s[:len(s) // 2], s[len(s) // 2:])
	diff = 0
	for c in 'abcdefghijklmnopqrstuvwxyz':
		diff += abs(a.count(c) - b.count(c))
	print(diff // 2)


n = int(input(''))

def process(string):
	string = str(string)
	n = len(string)
	if n % 2 == 1:
		return -1
	else:
		n1 = int(n / 2)
		n2 = 0
		a = string[0:n1]
		b = string[n1:n]
		for c in a:
			if c not in b:
				n2 = n2 + 1
			else:
				no = b.find(c)
				b = b.replace(c, ' ', 1)
	return n2
list1 = list()
for i in range(0, n):
	string = input('')
	list1.insert(i, string)
for i in range(0, n):
	string = list1[i]
	n1 = process(string)
	print(n1)


T = int(input())
for t in range(T):
	s = input()
	if len(s) & 1:
		print(-1)
	else:
		mid = int(len(s) / 2)
		a = s[0:mid]
		b = s[mid:]
		dic = {}
		for i in a:
			if i not in dic:
				dic[i] = 0
			dic[i] += 1
		for i in b:
			if i not in dic:
				dic[i] = 0
			dic[i] -= 1
		print(int(sum([abs(v) for v in dic.values()]) / 2))


firstinput = int(input())
if firstinput >= 1 and firstinput <= 100:
	T = firstinput
for i in range(T):
	secondinput = str(input())
	if len(secondinput) >= 1 and len(secondinput) <= 10000:
		concatenatedstring = secondinput
		a = concatenatedstring[:int(len(concatenatedstring) / 2)]
		b = concatenatedstring[int(len(concatenatedstring) / 2):]
		if len(a) != len(b):
			print(-1)
		else:
			count = 0
			for char in a:
				if char not in b:
					count = count + 1
				if char in b:
					b = b.replace(char, '', 1)
			print(count)


def Anagram(inpSt):
	if len(inpSt) % 2 == 0:
		st1 = [i for i in inpSt[0:int(len(inpSt) / 2)]]
		st2 = [i for i in inpSt[len(st1):]]
		for let in st1:
			if let in st2:
				st2.remove(let)
		return len(st2)
	return -1
T = int(input())
for i in range(T):
	print(Anagram(input()))


for i in range(int(input())):
	string = input()
	length = len(string)
	if length % 2 != 0:
		print(-1)
		continue
	count = 0
	length = length // 2
	left = list(string[0:length])
	right = list(string[length:])
	for letter in left:
		if letter in right:
			right.remove(letter)
		else:
			count += 1
	print(count)


import sys
sys.stdin.readline()

def letter_counts(s):
	counts = {}
	for c in s:
		counts[c] = counts.get(c, 0) + 1
	return counts
for line in sys.stdin.readlines():
	line = line.strip()
	l = len(line)
	if l % 2 != 0:
		print(-1)
	else:
		splitat = int(l / 2)
		a = line[:splitat]
		b = line[-splitat:]
		a_counts = letter_counts(a)
		b_counts = letter_counts(b)
		changes = 0
		for letter in b_counts.keys():
			a_count = a_counts.get(letter, 0)
			b_count = b_counts.get(letter)
			changes += max(0, b_count - a_count)
		print(changes)


from collections import Counter

def answer(s):
	(n, r) = divmod(len(s), 2)
	if r:
		return -1
	(a, b) = (Counter(s[:n]), Counter(s[n:]))
	return sum((max(0, a[x] - b[x]) for x in a))
for _ in range(int(input())):
	print(answer(input()))


test_cases = int(input())
for x in range(0, test_cases):
	line = input()
	if len(line) % 2 == 1:
		print(-1)
	else:
		string_length = int(len(line) / 2)
		first_string = line[0:string_length]
		second_string = line[string_length:string_length * 2]
		edit_distance = 0
		for letter in first_string:
			if letter in second_string:
				second_string = second_string.replace(letter, '', 1)
			else:
				edit_distance += 1
		print(edit_distance)


def getN(x):
	return ord(x) - ord('a')

def solve():
	s = input()
	l = len(s)
	if l % 2 == 1:
		print(-1)
		return
	la = [0 for i in range(0, 26)]
	lb = [0 for i in range(0, 26)]
	a = s[0:l // 2]
	b = s[l // 2:l]
	for i in a:
		la[getN(i)] += 1
	for i in b:
		lb[getN(i)] += 1
	re = 0
	for i in range(0, 26):
		if la[i] > lb[i]:
			re += lb[i]
		else:
			re += la[i]
	print(l // 2 - re)
t = int(input())
for i in range(0, t):
	solve()


import sys

def is_anagram(line):
	if len(line) % 2 == 1:
		print('-1')
		return
	brd = len(line) // 2
	l1 = line[0:brd]
	l2 = line[brd:]
	ano_dict = dict()
	for char in l1:
		if char in ano_dict:
			ano_dict[char] += 1
		else:
			ano_dict[char] = 1
	change_cntr = 0
	for char in l2:
		if char not in ano_dict or ano_dict[char] == 0:
			change_cntr += 1
		else:
			ano_dict[char] -= 1
	print(change_cntr)

def main():
	first = 1
	for line in sys.stdin:
		if first == 1:
			first = 0
		else:
			is_anagram(line.split()[0])
main()


t = int(input())
while t:
	t -= 1
	count = 0
	s = input()
	if len(s) % 2 == 0:
		s1 = s[:int(len(s) / 2)]
		s2 = s[int(len(s) / 2):]
		for i in range(0, len(s1)):
			if s1[i] in s2:
				s2 = s2.replace(s1[i], '', 1)
			else:
				count += 1
		print(count)
	else:
		print('-1')


T = int(input().strip())
for i in range(T):
	string = input().strip()
	if len(string) % 2 == 0:
		(A, B) = (string[:len(string) // 2], string[len(string) // 2:])
		count = 0
		for i in A:
			if i in B:
				B = B.replace(i, '', 1)
			else:
				count += 1
		print(count)
	else:
		print(-1)


T = int(input())

def letter_counts(a):
	counts = {}
	for letter in a:
		if letter in counts:
			counts[letter] += 1
		else:
			counts[letter] = 1
	return counts

def set_difference(a, b):
	if len(a) != len(b):
		return -1
	a_counts = letter_counts(a)
	b_counts = letter_counts(b)
	diffs = 0
	for key in set(list(a_counts.keys()) + list(b_counts.keys())):
		if key in a_counts and key in b_counts:
			diffs += abs(a_counts[key] - b_counts[key])
		elif key in a_counts:
			diffs += a_counts[key]
		else:
			diffs += b_counts[key]
	return diffs // 2
for i in range(T):
	ar = list(input())
	a = ar[:len(ar) // 2]
	b = ar[len(ar) // 2:]
	print(set_difference(a, b))


from collections import Counter
test = int(input())
out = []
for j in range(test):
	word = list(input())
	wo = len(word) // 2
	a = word[:wo]
	b = word[wo:]
	a.sort()
	b.sort()
	if len(word) % 2 != 0:
		out.append(-1)
	else:
		a = Counter(a)
		b = Counter(b)
		new = list((a - b).elements())
		out.append(len(new))
out.reverse()
while len(out) != 0:
	print(out.pop())