One day Alice visited Byteland to purchase jewels for her upcoming wedding anniversary.
In Byteland, every Jewelry shop has their own discount methods to attract the customers. One discount method called Buy1-Get1 caught Alice's attention. That is, Alice buys one jewel, then she can get one additional jewel with the same color without charge by Buy1-Get1. 
Alice lists the needed jewels as a string S, each letter denotes one jewel, and the same letters denote the same colors of jewels, and the different letters denote the different colors of jewels. The cost of each jewel is 1. Your task is to calculate the minimum cost for getting all the jewels Alice listed.

------ Input ------ 

The first line of input contains a single line T, which represents the number of test cases. Then T lines will follow, and each contains a string S, which represents the jewels Alice needed.

------ Output ------ 

Output the minimum cost for each test case.

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

1 ≤ T ≤ 100
1 ≤ |S| ≤ 200, where |S| represents the length of the string S. 
The string S is case sensitive, and will contain only English characters in the range [a-z], [A-Z].

----- Sample Input 1 ------ 
4
ssss
ssas
sa
s
----- Sample Output 1 ------ 
2
3
2
1
----- explanation 1 ------ 
In the first sample case, Alice needs 4 jewel of color s. One of the optimal way is the following: Buy the first s with cost 1, and she can get the second s without charge. Then buy the third s with cost 1, and she can get the last s without charge. In this case, she get 4 jewels with only cost 2.
In the second sample case, Alice needs 3 jewels of color s and 1 jewel of color a. One of the optimal way is the following: Buy the second s with cost 1, and she can get the last s without charge. Then buy the a and the first s with cost 2. In this case, she get 4 jewels with only cost 3.
In the third and fourth sample cases, she cannot save her money by using Buy1-Get1.

Difficulty: EASY
Tags: Ad-hoc

Starter code:

Solutions:
import math
for i in range(int(input())):
	x = input().strip()
	x1 = set(x)
	c = 0
	for k in x1:
		c += math.ceil(x.count(k) / 2)
	print(c)


import math
from collections import Counter
for tc in range(int(input())):
	s = input().strip()
	c = set(s)
	tot = 0
	for i in c:
		tot += math.ceil(s.count(i) / 2)
	print(tot)


t = int(input())
for i in range(t):
	s = input().strip()
	s = list(s)
	d = {}
	cost = 0
	for i in s:
		d[i] = s.count(i)
	for j in d:
		if d[j] % 2 == 0:
			cost = cost + d[j] // 2
		else:
			cost = cost + d[j] // 2 + 1
	print(cost)


import math
T = int(input())
for i in range(T):
	S = input().strip()
	Set_S = set(S)
	cost = 0
	for j in Set_S:
		cost = cost + math.ceil(S.count(j) / 2)
	print(cost)


for _ in range(int(input())):
	x = list(input().strip())
	s = set(x)
	cost = 0
	for i in s:
		cost += x.count(i) // 2 + x.count(i) % 2
	print(cost)


from math import ceil
for i in range(int(input())):
	s = input().strip()
	unique = set(s)
	total = 0
	for i in unique:
		if s.count(i) % 2 == 0:
			total += s.count(i) // 2
		else:
			total += s.count(i) // 2 + 1
	print(total)


import math
t = int(input())
while t > 0:
	s = input().strip()
	st = set(s)
	res = 0
	for i in st:
		res = res + math.ceil(s.count(i) / 2)
	print(res)
	t = t - 1


import math
t = int(input())
for _ in range(t):
	s = input()
	l = list(s.strip())
	set1 = set(l)
	cost = 0
	for i in set1:
		cost += math.ceil(l.count(i) / 2)
	print(cost)


for _ in range(int(input())):
	l = input()
	s = list(l.strip())
	s1 = set(s)
	s2 = 0
	for i in s1:
		if s.count(i) % 2 == 0:
			a = s.count(i) // 2
		else:
			a = s.count(i) // 2 + 1
		s2 = s2 + a
	print(s2)


from collections import Counter
from math import ceil
for i in range(int(input())):
	s = Counter(input().strip())
	r = 0
	for i in s:
		r += s[i] // 2 + s[i] % 2
	print(r)


from collections import Counter
for _ in range(int(input())):
	A = list(input().strip())
	B = Counter(A)
	cost = 0
	for b in B:
		cost += B[b] // 2 + (B[b] % 2 > 0)
	print(cost)


import math
t = int(input())
for x in range(t):
	s = input().strip()
	s1 = set(s)
	total = 0
	for i in s1:
		total = total + math.ceil(s.count(i) / 2)
	print(total)


t_case = int(input())
for i in range(t_case):
	cost = 0
	jw = input().strip()
	jw_li = []
	for i in jw:
		if i not in jw_li:
			jw_li.append(i)
		else:
			jw_li.pop(jw_li.index(i))
			cost += 1
	print(cost + len(jw_li))


import math
n = int(input())
for i in range(n):
	a = input().strip()
	l = 0
	for i in set(a):
		l = l + math.ceil(a.count(i) / 2)
	print(l)


for _ in range(int(input())):
	s = input()
	l = list(s.strip())
	set1 = set(l)
	cost = 0
	for i in set1:
		if l.count(i) % 2 == 0:
			a = l.count(i) // 2
		else:
			a = l.count(i) // 2 + 1
		cost = cost + a
	print(cost)


t = int(input())
for i in range(t):
	s = input().strip()
	dic = {}
	for j in s:
		dic[j] = dic.get(j, 0) + 1
	cost = 0
	for j in dic:
		cost = cost + dic[j] // 2 + dic[j] % 2
	print(cost)


t = int(input())
for i in range(t):
	s = input().strip()
	lst = []
	l1 = []
	l2 = []
	for i in s:
		lst.append(i)
	lst.sort()
	l = len(lst)
	lst.append(' ')
	while l != 0:
		if lst[0] == lst[1]:
			l1.append(lst[0])
			lst.remove(lst[0])
			lst.remove(lst[0])
			l -= 2
		else:
			l2.append(lst[0])
			lst.remove(lst[0])
			l -= 1
	print(len(l1) + len(l2))


import math
for t in range(int(input())):
	s = input().strip()
	count = 0
	s = list(s)
	s1 = set(s)
	for i in s1:
		count += s.count(i) // 2 + s.count(i) % 2
	print(count)


import math
T = int(input())
for i in range(T):
	S = input().strip()
	c = 1
	s = 0
	d = 0
	l1 = set(S)
	for j in l1:
		c = S.count(j)
		d = math.ceil(c / 2)
		s += d
	print(s)


import math
for _ in range(int(input())):
	s = input().strip()
	c = set(s)
	x = 0
	for i in c:
		x += math.ceil(s.count(i) / 2)
	print(x)


from math import ceil
t = int(input())
for i in range(t):
	s = input().strip()
	s1 = set(s)
	c = 0
	for j in s1:
		c = c + ceil(s.count(j) / 2)
	print(c)


from math import ceil
for i in range(int(input())):
	string = input().strip()
	arr = set(string)
	ans = 0
	for x in arr:
		ans += ceil(string.count(x) / 2)
	print(ans)


import math
t = int(input())
while t > 0:
	s = input().strip()
	s1 = set(s)
	c = 0
	for i in s1:
		c = c + math.ceil(s.count(i) / 2)
	print(c)
	t = t - 1


def solve():
	dic = {}
	string = input().strip()
	for i in string:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	ans = 0
	for i in dic.keys():
		ans += dic[i] // 2
		ans += dic[i] % 2
	print(ans)
t = int(input())
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	s = input().strip()
	count = 0
	s = list(s)
	s1 = set(s)
	for i in s1:
		count += s.count(i) // 2 + s.count(i) % 2
	print(count)


for _ in range(int(input())):
	s = list(input().strip())
	se = list(set(s))
	c = 0
	for i in se:
		c += s.count(i) // 2 + s.count(i) % 2
	print(c)


from collections import Counter
t = int(input())
for _ in range(t):
	s = input().strip()
	counts = Counter(s)
	total_cost = 0
	for count in counts.values():
		cost = (count + 1) // 2
		total_cost += cost
	print(total_cost)


def s():
	d = {}
	S = input().strip()
	for i in S:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	a = 0
	for i in d.keys():
		a += d[i] // 2
		a += d[i] % 2
	print(a)
T = int(input())
while T:
	s()
	T -= 1


import math
n = int(input())
for i in range(n):
	s = input().strip()
	l = set(list(s))
	c = 0
	for i in l:
		d = s.count(i)
		c += math.ceil(d / 2)
	print(c)


t = int(input())
for _ in range(t):
	s = input().strip()
	d = {}
	cost = 0
	for i in s:
		d[i] = 0
	for j in s:
		d[j] += 1
	for z in d:
		if d[z] % 2 == 0:
			cost += d[z] // 2
		else:
			cost += d[z] // 2 + 1
	print(cost)


T = int(input())
for k in range(T):
	s = input()
	a = list(s.strip())
	b = set(a)
	count = 0
	counts = 0
	for i in b:
		if a.count(i) % 2 == 0:
			count = count + a.count(i) // 2
		elif a.count(i) % 2 == 1:
			count = count + (a.count(i) // 2 + 1)
	print(count)


alphabet = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0, 'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0, 'H': 0, 'I': 0, 'J': 0, 'K': 0, 'L': 0, 'M': 0, 'N': 0, 'O': 0, 'P': 0, 'Q': 0, 'R': 0, 'S': 0, 'T': 0, 'U': 0, 'V': 0, 'W': 0, 'X': 0, 'Y': 0, 'Z': 0}
t = int(input())
for i in range(t):
	buy_elems = input()
	s = ''.join(filter(str.isalpha, buy_elems))
	for j in s:
		alphabet[j] += 1
	result = 0
	for (key, value) in alphabet.items():
		result += value // 2 + value % 2
		alphabet[key] = 0
	print(result)


import math
t = int(input())
for _ in range(t):
	n = 0
	s = input().strip()
	for i in set(s):
		n += math.ceil(s.count(i) / 2)
	print(n)


from collections import Counter
for i in range(int(input())):
	s = input()
	s = s.strip()
	a = Counter(s)
	count = 0
	for i in a:
		if a[i] % 2 == 0:
			count += a[i] // 2
		else:
			count += a[i] // 2 + 1
	print(count)


for _ in range(int(input())):
	s = input().strip()
	a = set(map(str, s))
	res = 0
	for i in a:
		x = s.count(i)
		res += x // 2 + x % 2
	print(res)


import math
n = int(input())
for i in range(n):
	s = input().strip()
	l = list(s)
	count = 0
	d = {}
	for j in l:
		if j in d:
			d[j] += 1
		else:
			d[j] = 1
	for (k, v) in d.items():
		if v % 2 == 0:
			count += v // 2
		else:
			r = math.ceil(v / 2)
			count += r
	print(count)


from collections import Counter
for tc in range(int(input())):
	s = input().strip()
	c = Counter(s)
	tot = 0
	for i in c.values():
		tot = tot + i // 2 + i % 2
	print(tot)


from collections import Counter
for _ in range(int(input())):
	s = input()
	s = s.strip()
	d = Counter(s)
	s1 = 0
	for i in d:
		if d[i] % 2 == 0:
			s1 += d[i] // 2
		else:
			s1 += d[i] // 2 + 1
	print(s1)


T = int(input())
for i in range(T):
	s = input().strip()
	l = []
	for j in s:
		if j not in l:
			l.append(j)
	p = 0
	for j in l:
		if s.count(j) % 2 == 0:
			p += s.count(j) // 2
		else:
			p += s.count(j) // 2 + 1
	print(p)


for _ in range(int(input())):
	x = list(input().strip())
	xe = set(x)
	d = {}
	cost = 0
	for i in xe:
		d[i] = x.count(i)
	for i in d:
		cost += d[i] // 2 + d[i] % 2
	print(cost)


from math import ceil
for _ in range(int(input())):
	s = input().strip()
	l = set(s)
	count = 0
	for i in l:
		count += ceil(s.count(i) / 2)
	print(count)


t = int(input())
for i in range(t):
	s = input().strip()
	s = list(s)
	uniq = set(s)
	cost = 0
	for i in uniq:
		cost = cost + (s.count(i) // 2 + s.count(i) % 2)
	print(cost)


import math
n = int(input())
for i in range(n):
	p = input().strip()
	k = set(p)
	c = 0
	for i in k:
		c += math.ceil(p.count(i) / 2)
	print(c)


import math
for i in range(int(input())):
	s = input().strip()
	s1 = set(s)
	sm = 0
	for j in s1:
		sm += math.ceil(s.count(j) / 2)
	print(sm)


for _ in range(int(input())):
	x = list(input().strip())
	cost = 0
	d = {}
	for i in x:
		d[i] = x.count(i)
	for i in d:
		if d[i] % 2 == 0:
			cost += d[i] // 2
		else:
			cost += d[i] // 2
			cost += 1
	print(cost)