A string $a=a_1a_2\dots a_n$ is called even if it consists of a concatenation (joining) of strings of length $2$ consisting of the same characters. In other words, a string $a$ is even if two conditions are satisfied at the same time:

its length $n$ is even;

for all odd $i$ ($1 \le i \le n - 1$), $a_i = a_{i+1}$ is satisfied.

For example, the following strings are even: "" (empty string), "tt", "aabb", "oooo", and "ttrrrroouuuuuuuukk". The following strings are not even: "aaa", "abab" and "abba".

Given a string $s$ consisting of lowercase Latin letters. Find the minimum number of characters to remove from the string $s$ to make it even. The deleted characters do not have to be consecutive.


-----Input-----

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

The descriptions of the test cases follow.

Each test case consists of one string $s$ ($1 \le |s| \le 2 \cdot 10^5$), where $|s|$ — the length of the string $s$. The string consists of lowercase Latin letters.

It is guaranteed that the sum of $|s|$ on all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print a single number — the minimum number of characters that must be removed to make $s$ even.


-----Examples-----

Input
6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw
Output
3
3
2
0
2
7


-----Note-----

In the first test case you can remove the characters with indices $6$, $7$, and $9$ to get an even string "aabbddcc".

In the second test case, each character occurs exactly once, so in order to get an even string, you must remove all characters from the string.

In the third test case, you can get an even string "aaaabb" by removing, for example, $4$-th and $6$-th characters, or a string "aabbbb" by removing the $5$-th character and any of the first three.

Difficulty: EASY
Tags: String algorithms

Dynamic programming

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
T = int(input())
q = []
for i in range(T):
	s = input()
	q.append(s)

def solve(s):
	st = set()
	sum = 0
	for c in s:
		if c in st:
			sum += len(st) - 1
			st = set()
		else:
			st.add(c)
	sum += len(st)
	print(sum)
for s in q:
	solve(s)


number = int(input())
tests = []
for i in range(number):
	soz = input()
	tests.append(soz)
for test in tests:
	queue = []
	cnt = 0
	for ch in test:
		if len(queue) == 0:
			queue.append(ch)
		elif ch in queue:
			queue = []
			cnt += 2
		else:
			queue.append(ch)
	print(len(test) - cnt)


import math
import sys
from collections import deque
import heapq

def inp():
	return sys.stdin.readline().rstrip()

def mpp():
	return map(int, inp().split())

def lis():
	return list(mpp())

def sol(s):
	v = set()
	n = len(s)
	new = ''
	i = 0
	j = 1
	v.add(s[i])
	while i < n and j < n:
		if s[j] in v:
			new += s[j] + s[j]
			v.clear()
			i = j + 1
			if i < n:
				v.add(s[i])
			else:
				break
			j = i + 1
		else:
			v.add(s[j])
			j += 1
	return len(s) - len(new)

def main():
	t = int(inp())
	for _ in range(t):
		s = inp()
		print(sol(s))
main()


def func():
	s = input()
	d = {}
	k = 0
	n = len(s)
	for i in s:
		if i in d.keys():
			if d[i] == 1:
				k += 2
				d = {}
		else:
			d[i] = 1
	return n - k
t = int(input())
L = []
for i in range(t):
	y = func()
	L.append(y)
for i in L:
	print(i)


def main():
	s = input()
	n = len(s)
	sset = set()
	l = 0
	for z in s:
		if z in sset:
			l += 2
			sset = set()
		else:
			sset.add(z)
	return n - l
for _ in range(int(input())):
	print(main())


def solve():
	s = input()
	st = set()
	ans = 0
	for i in range(len(s)):
		if s[i] in st:
			ans += 2
			st = set()
		else:
			st.add(s[i])
	print(abs(len(s) - ans))
tst = int(input())
for i in range(tst):
	solve()


import sys
import math
import itertools
mod = 998244353

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def rls():
	return list(map(str, input().split()))

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

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def nextPowerOf2(n):
	n -= 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n += 1
	return n

def highestPowerof2(x):
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	return x ^ x >> 1
for _ in range(ri()):
	s = input()
	st = set()
	ans = 0
	for i in s:
		if i in st:
			ans += 2
			st = set()
		else:
			st.add(i)
	print(len(s) - ans)


def solve():
	a = input()
	c = len(a)
	s = set()
	for i in a:
		if i in s:
			c -= 2
			s = set()
		else:
			s |= {i}
	print(c)
t = 1
t = int(input())
while t > 0:
	solve()
	t -= 1


def main():
	for i in range(int(input())):
		input_str = input()
		emp_dict = {}
		ans = len(input_str)
		for j in range(len(input_str)):
			if input_str[j] in emp_dict:
				ans -= 2
				emp_dict = {}
			else:
				emp_dict[input_str[j]] = 1
		print(ans)
main()


def read():
	str = input()
	return str

def solve(str):
	num = 0
	n = len(str)
	char_set = set()
	for c in str:
		if c in char_set:
			num += 2
			char_set.clear()
		else:
			char_set.add(c)
	return n - num

def output(ans):
	print(ans)
	pass
T = eval(input())
for i in range(T):
	str = read()
	ans = solve(str)
	output(ans)
pass


import math

def main_function():
	test_cases = range(int(input()))
	for test_case in test_cases:
		s = input()
		counter = 0
		odd_mode_on = True
		hashy = {}
		for i in range(len(s)):
			if s[i] not in hashy:
				hashy[s[i]] = 1
			else:
				counter += len(hashy) - 1
				hashy = {}
		counter += len(hashy)
		print(counter)
main_function()


for i in range(int(input())):
	s = input()
	s1 = ''
	l = len(s)
	for j in s:
		if j in s1:
			l -= 2
			s1 = ''
		else:
			s1 = s1 + j
	print(l)


for t in range(int(input())):
	s = input()
	n = len(s)
	cs = ''
	for i in s:
		if i in cs:
			cs = ''
			n -= 2
		else:
			cs += i
	print(n)


def even_string(s):
	n = len(s)
	c = 0
	st = ''
	for i in s:
		if i in st:
			st = ''
			c -= 1
		else:
			st += i
			c += 1
	return c
t = int(input())
for i in range(t):
	s = input()
	print(even_string(s))


for _ in range(int(input())):
	b = input()
	c = set()
	s = len(b)
	i = 0
	for i in b:
		if i not in c:
			c.add(i)
		else:
			s -= 2
			c.clear()
	print(s)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	stack = []
	for i in s:
		if i in stack:
			n -= 2
			stack = []
		else:
			stack.append(i)
	print(n)


n = int(input())
for _ in range(n):
	s = input()
	res = len(s)
	temp = ''
	for i in s:
		if i in temp:
			res -= 2
			temp = ''
		else:
			temp += i
	print(res)


from sys import stdin, stdout
from collections import defaultdict
import math
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	s = input().strip()
	s = list(s)
	d = defaultdict(lambda : 0)
	ans = 0
	for ch in s:
		d[ch] += 1
		if d[ch] == 2:
			ans += 1
			d.clear()
	print(len(s) - 2 * ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	s2 = ''
	for i in s:
		if i in s2:
			n -= 2
			s2 = ''
		else:
			s2 += i
	print(n)


def main():
	t = int(input())
	for _ in range(t):
		str_input = list(input())
		vet = []
		total = 0
		for c in str_input:
			if c in vet:
				total += len(vet) - 1
				vet = []
			else:
				vet.append(c)
		total += len(vet)
		print(total)
main()


t = int(input())
for i in range(t):
	str = input()
	arr = []
	count = 0
	for i in str:
		if i in arr:
			count += len(arr) - 1
			arr = []
		else:
			arr.append(i)
	print(count + len(arr))


for _ in range(int(input())):
	s = input()
	last = {}
	ans = 0
	for (i, x) in enumerate(s):
		if x in last:
			ans += len(last) - 1
			last = {}
		else:
			last[x] = i
	ans += len(last)
	print(ans)


n = int(input())
for i in range(n):
	word = input()
	l = []
	c = 0
	for i in word:
		if i in l:
			c += len(l) - 1
			l = []
		else:
			l.append(i)
	print(c + len(l))


t = int(input())
for i in range(t):
	s = input()
	ans = len(s)
	S = set()
	for j in s:
		if j not in S:
			S.add(j)
		else:
			ans -= 2
			S.clear()
	print(ans)


for _ in range(int(input())):
	s = input()
	dict_s = {}
	r = len(s)
	for i in s:
		if i in dict_s:
			r = r - 2
			dict_s = {}
		else:
			dict_s[i] = 1
	print(r)


for _ in range(int(input())):
	a = input()
	s = set()
	c = len(a)
	for i in a:
		if i in s:
			c -= 2
			s = set()
		else:
			s.add(i)
	print(c)


for _ in range(int(input())):
	s = list(input())
	res = len(s)
	d = set()
	for i in s:
		if i in d:
			res -= 2
			d.clear()
		else:
			d.add(i)
	print(res)


n = int(input())
for i in range(n):
	s = input()
	a = ''
	l = len(s)
	for i in s:
		if i in a:
			l = l - 2
			a = ''
		else:
			a = a + i
	print(l)


t = int(input())
for _ in range(t):
	s = input().strip()
	(n, m) = (len(s), 0)
	a = ''
	for i in s:
		if i in a:
			m += 2
			a = ''
		else:
			a += i
	print(n - m)


import sys
import math
from bisect import bisect_right as br

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	st = input()
	ans = 0
	s = set()
	for i in range(len(st)):
		if st[i] in s:
			ans += len(s) - 1
			s = set()
		else:
			s.add(st[i])
	ans += len(s)
	print(ans)


t = int(input())
for i in range(0, t):
	s = input()
	ans = 0
	li = []
	for x in s:
		if x in li:
			ans += len(li) - 1
			li.clear()
		else:
			li.append(x)
	print(ans + len(li))


from typing import Set
n = int(input())
strings = []
for i in range(n):
	strings.append(input())
for s in strings:
	ans = 0
	setLetters = set()
	for i in range(len(s)):
		if s[i] in setLetters:
			ans += len(setLetters) - 1
			setLetters.clear()
		else:
			setLetters.add(s[i])
	ans += len(setLetters)
	print(ans)


def process_string(s):
	total = 0
	reg = dict()
	for c in s:
		if c in reg:
			total += 2
			reg = dict()
		else:
			reg[c] = True
	return total
for _ in range(int(input())):
	string = input()
	print(len(string) - process_string(string))


meow = int(input())
for _ in range(meow):
	word = input()
	new = ''
	ans = 0
	for i in word:
		if i not in new:
			new += i
		else:
			new = ''
			ans += 2
	print(len(word) - ans)


for _ in range(int(input())):
	s = input()
	d = {}
	ans = len(s)
	for i in range(len(s)):
		if s[i] in d:
			ans -= 2
			d = {}
		else:
			d[s[i]] = 1
	print(ans)


def solve(s):
	cur_count = 0
	seen = set()
	ans = 0
	for char in s:
		if char not in seen:
			seen.add(char)
			cur_count += 1
		else:
			ans += cur_count - 1
			seen = set()
			cur_count = 0
	ans += cur_count
	return ans
T = int(input())
for num_experiment in range(1, T + 1):
	s = input()
	ans = solve(s)
	print(ans)


from collections import Counter

def check(s):
	data = []
	total = 0
	for i in range(len(s)):
		if s[i] not in data:
			data.append(s[i])
		else:
			total += len(data) - 1
			data.clear()
	return total + len(data)
for _ in range(int(input())):
	s = input()
	print(check(s))


tc = int(input())
for _ in range(tc):
	s = input()
	n = len(s)
	track = set()
	ans = 0
	i = 0
	for i in range(n):
		if s[i] in track:
			ans += len(track) - 1
			track = set()
		else:
			track.add(s[i])
	print(ans + len(track))


n = int(input())
for _ in range(n):
	s = input()
	ans = 0
	curr = set()
	for c in s:
		if c not in curr:
			curr.add(c)
		else:
			ans += len(curr) - 1
			curr = set()
	ans += len(curr)
	print(ans)


for _ in range(int(input())):
	(a, s, c) = (input(), set(), 0)
	for i in a:
		if i in s:
			c += len(s) - 1
			s = set()
		else:
			s.add(i)
	print(c + len(s))


for _ in range(int(input())):
	(s, l, c) = (input(), [], 0)
	for i in s:
		if i in l:
			c += len(l) - 1
			l = []
		else:
			l.append(i)
	print(c + len(l))


for _ in range(int(input())):
	string = input()
	count = 0
	pairs = set()
	for char in string:
		count += 1
		if char in pairs:
			pairs = set()
			count -= 2
		else:
			pairs.add(char)
	print(count)


for _ in range(int(input())):
	(a, s, c) = (input(), list(), 0)
	for i in a:
		if i in s:
			c += len(s) - 1
			s = list()
		else:
			s.append(i)
	print(c + len(s))


for _ in range(int(input())):
	s = str(input())
	d = 0
	arr = []
	for item in s:
		if item in arr:
			d = d + len(arr) - 1
			arr = []
		else:
			arr.append(item)
	print(d + len(arr))


for _ in range(int(input())):
	(s, l, count) = (input(), '', 0)
	for i in s:
		if i in l:
			count += len(l) - 1
			l = ''
		else:
			l += i
	print(count + len(l))


for _ in range(int(input())):
	s = input()
	se = set()
	ans = len(s)
	for i in s:
		if i not in se:
			se.add(i)
		else:
			ans -= 2
			se.clear()
			se = set()
	print(ans)


for _ in range(int(input())):
	s = input()
	l = []
	ans = 0
	for i in s:
		if i not in l:
			l.append(i)
		else:
			ans += len(l) - 1
			l = []
	print(ans + len(l))


from collections import Counter
n = input()

def solve(s):
	a = []
	res = 0
	for i in s:
		if i in a:
			res += len(a) - 1
			a = []
		else:
			a.append(i)
	return res + len(a)
for i in range(int(n)):
	s = input()
	print(solve(s))


t = int(input())
for _ in range(t):
	s = input()
	l = []
	ans = 0
	for k in s:
		if k in l:
			ans = ans + len(l) - 1
			l = []
		else:
			l.append(k)
	ans = ans + len(l)
	print(ans)


for _ in range(int(input())):
	s = input()
	set_s = set()
	r = 0
	for i in s:
		if i in set_s:
			r = r + len(set_s) - 1
			set_s = set()
		else:
			set_s.add(i)
	print(r + len(set_s))


T = int(input())

def solve(S):
	N = len(S)
	M = 0
	prev = [0] * 26
	for c in S:
		if prev[ord(c) - 97]:
			prev[ord(c) - 97] = 0
			M += 2
			prev = [0] * 26
		else:
			prev[ord(c) - 97] = 1
	print(N - M)
for _ in range(T):
	s = input()
	solve(s)


for t in range(int(input())):
	m = input()
	k = set()
	o = 0
	for z in m:
		if z in k:
			o += len(k) - 1
			k = set()
		else:
			k.add(z)
	print(o + len(k))


for i in range(int(input())):
	arr = input()
	st = set()
	OTBET = 0
	for e in arr:
		if e in st:
			OTBET += len(st) - 1
			st.clear()
		else:
			st.add(e)
	print(OTBET + len(st))


for i in range(int(input())):
	s = input()
	arr = []
	count = 0
	for c in s:
		if c in arr:
			count += len(arr) - 1
			arr = []
		else:
			arr.append(c)
	count += len(arr)
	print(count)


def solve():
	s = input()
	n = len(s)
	memo = dict()
	pairs = 0
	for i in range(n):
		if memo.get(s[i]):
			pairs += 1
			memo = dict()
		else:
			memo[s[i]] = 1
	print(n - 2 * pairs)
t = int(input())
while t > 0:
	t -= 1
	solve()


for __ in range(int(input())):
	word = input()
	s = set()
	l = 0
	for w in word:
		if w in s:
			l += 2
			s = set()
		else:
			s.add(w)
	print(len(word) - l)


for _ in range(int(input())):
	s = input()
	ans = len(s)
	a1 = set()
	for j in s:
		if j not in a1:
			a1.add(j)
		else:
			ans -= 2
			a1.clear()
	print(ans)


for _ in [0] * int(input()):
	slen = out = 0
	a = ''
	for i in input():
		if i not in a:
			a = a + i
		else:
			out = out + 2
			a = ''
		slen = slen + 1
	print(slen - out)


num = int(input())
while num > 0:
	s = input()
	m = {}
	par = 0
	for c in s:
		if m.get(c):
			par = par + 2
			m.clear()
		else:
			m[c] = c
	print(len(s) - par, end='\n')
	num = num - 1


qtd_casos_teste = int(input())
for i in range(qtd_casos_teste):
	string_teste = input()
	s1 = ''
	qtd_caracteres_remover = len(string_teste)
	for j in string_teste:
		if j in s1:
			qtd_caracteres_remover -= 2
			s1 = ''
		else:
			s1 = s1 + j
	print(qtd_caracteres_remover)


for _ in range(int(input())):
	s = input()
	l = len(s)
	u = ''
	for i in s:
		if i in u:
			l = l - 2
			u = ''
		else:
			u = u + i
	print(l)


for __ in range(int(input())):
	king = input()
	one = set()
	two = 0
	for l in king:
		if l in one:
			two += 2
			one = set()
		else:
			one.add(l)
	print(len(king) - two)


t = int(input())
for _ in range(t):
	s = list(input())
	open = ''
	total = 0
	for ch in s:
		if ch not in open:
			open += ch
		else:
			total += len(open) - 1
			open = ''
	total += len(open)
	print(total)


for t in range(int(input())):
	s = input()
	a = ''
	ans = 0
	for i in s:
		if i not in a:
			a += i
		else:
			ans += 2
			a = ''
	print(len(s) - ans)


for _ in range(int(input())):
	s = input()
	ans = 0
	t = ''
	for c in s:
		if not c in t:
			t += c
			ans += 1
		else:
			t = ''
			ans -= 1
	print(ans)


for _ in range(int(input())):
	s = input()
	seen = set()
	i = 0
	ans = 0
	while i < len(s):
		if s[i] in seen:
			ans += 2
			seen = set()
		else:
			seen.add(s[i])
		i += 1
	print(len(s) - ans)


import math
t = int(input())
for _ in range(t):
	s = input()
	s1 = set()
	count = 0
	for c in s:
		if not s1:
			s1.add(c)
		elif c in s1:
			count += len(s1) - 1
			s1 = set()
		else:
			s1.add(c)
	print(count + len(s1))


for _ in range(int(input())):
	s = input()
	st = set()
	ans = 0
	for i in s:
		if i in st:
			ans += 2
			st = set()
		else:
			st.add(i)
	print(len(s) - ans)


def minoperations(s):
	n = len(s)
	f = [0] * 26
	ans = 0
	for c in s:
		if f[ord(c) - ord('a')]:
			ans += 2
			f = [0] * 26
		else:
			f[ord(c) - ord('a')] = 1
	return n - ans
t = int(input())
for _ in range(t):
	s = input()
	print(minoperations(s))


def endpoint(string, start, end):
	letters = []
	for i in range(start, end):
		if string[i] in letters:
			return i
		letters.append(string[i])
	return -1
t = int(input())
output = []
for i in range(t):
	string = input()
	n = len(string)
	pos = -1
	pairs = 0
	while 1 == 1:
		pos = endpoint(string, pos + 1, n)
		if pos == -1:
			break
		pairs += 1
	output.append(n - pairs * 2)
for i in range(t):
	print(output[i])


n = int(input())
for _ in range(n):
	x = input()
	res = 0
	mp = {}
	for i in range(len(x)):
		if x[i] in mp:
			res += 2
			mp.clear()
		else:
			mp[x[i]] = 1
	print(len(x) - res)


for _ in range(int(input())):
	line = input()
	n = len(line)
	wset = set()
	recorded = 0
	for ch in line:
		if ch in wset:
			recorded += 2
			wset = set()
		else:
			wset.add(ch)
	print(n - recorded)


_ = int(input())
for __ in range(_):
	word = input()
	s = set()
	out = 0
	for letter in word:
		if letter in s:
			out += 2
			s = set()
		else:
			s.add(letter)
	print(len(word) - out)


def c(a):
	prev = [0] * 26
	m = 0
	mas = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	for i in range(len(a)):
		b = mas.index(a[i])
		if prev[b] == 0:
			prev[b] = 1
		else:
			prev = [0] * 26
			m += 2
	return len(a) - m
a = int(input())
for i in range(a):
	b = input()
	print(c(b))


from collections import defaultdict
import sys

def input():
	return sys.stdin.readline().rstrip()
t = int(input())
for _ in range(t):
	dic = defaultdict(int)
	s = input()
	sol = 0
	idx = 0
	for i in range(len(s)):
		if dic[s[i]]:
			dic[s[i]] -= 1
			sol += sum(dic.values())
			dic = defaultdict(int)
		else:
			dic[s[i]] += 1
	sol += sum(dic.values())
	print(sol)


T = int(input())
for K in range(T):
	a = input()
	l = []
	r = []
	f = 0
	for i in a:
		if not l.__contains__(i):
			l.append(i)
		else:
			l.remove(i)
			r.extend(l)
			l.clear()
	r.extend(l)
	print(len(r))


l = []
n = int(input())
c = 0
for i in range(n):
	s = input()
	for i in s:
		if i not in l:
			l.append(i)
			c += 1
		else:
			c -= 1
			l = []
	print(c)
	l = []
	c = 0