An input string S of length N is transferred through the network using a special protocol. The protocol can send the string through a series of operations. In one operation, we can choose a lowercase english alphabet C and do one of the following:

Transfer 1 copy of C through the network.
Transfer 2 copies of C through the network.

Each of the above transfers take 1 unit of time.

Find the minimum time in which we can transfer the entire string S through the network.

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

- The first line will contain T - the number of test cases. Then the test cases follow.
- First line of each test case contains N - the length of the string S. 
- Second line of each test case contains the string S.

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

For each test case, output in a single line, the minimum time required to transfer the string. 

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $10^{5}$. 
- String $S$ contains lowercase english alphabets only.

----- Sample Input 1 ------ 
2
5
cbcdc
6
aabeee

----- Sample Output 1 ------ 
5
4

----- explanation 1 ------ 
Test Case $1$: String can be transferred through following operations: send $1$ copy of character $\texttt{c}$, send $1$ copy of character $\texttt{b}$, send $1$ copy of character $\texttt{c}$, send $1$ copy of character $\texttt{d}$, and send $1$ copy of character $\texttt{c}$. Thus, total $5$ operations are required. 

Test Case $2$: String can be transferred through following operations: send $2$ copies of character $\texttt{a}$, send $1$ copy of character $\texttt{b}$, send $1$ copy of character $\texttt{e}$, and send $2$ copies of character $\texttt{e}$. Thus, total $4$ operations are required.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for bunny in range(t):
	n = int(input())
	s = input()
	count = 0
	i = 0
	while i < n:
		if i + 1 < n and s[i] == s[i + 1]:
			count += 1
			i += 2
		else:
			count += 1
			i += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	while c < len(s) - 1:
		if s[c] == s[c + 1]:
			c += 2
			n -= 1
		else:
			c += 1
	print(n)


for i in range(int(input())):
	n = int(input())
	s = input()
	a = set(s)
	counter = 0
	for let in a:
		x = s.count(let)
		mult = s.count(let + let)
		counter += x - mult * 2 + mult
	print(counter)


for i in range(int(input())):
	num = int(input())
	inp = input()
	let = set(inp)
	c = 0
	for j in let:
		c += inp.count(j * 2) + inp.replace(j * 2, '').count(j)
	print(c)


t = int(input())
for e in range(t):
	N = int(input())
	d = input()
	c = 0
	while c < len(d) - 1:
		if d[c] == d[c + 1]:
			c = c + 2
			N = N - 1
		else:
			c = c + 1
	print(N)


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	i = 0
	while True:
		if i + 1 < len(s) and s[i] == s[i + 1]:
			c += 1
			i += 2
		else:
			c += 1
			i += 1
		if i >= len(s):
			break
	print(c)


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	j = 0
	while j < n - 1:
		if s[j] == s[j + 1]:
			j += 1
		j += 1
		c += 1
	if j < n:
		c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in set(s):
		c += s.count(i + i)
	print(n - c)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	while c < len(s) - 1:
		if s[c] == s[c + 1]:
			c += 2
			n -= 1
		else:
			c += 1
	print(n)


for _ in range(int(input())):
	n = int(input())
	str = input()
	i = 0
	cnt = 0
	first_index = 0
	while i < n:
		if i - 1 >= first_index and str[i] == str[i - 1]:
			first_index = i + 1
		else:
			cnt += 1
		i += 1
	print(cnt)


for _ in range(int(input())):
	x = int(input())
	y = input()
	ans = 1
	list1 = []
	for i in range(len(y) - 1):
		if y[i] == y[i + 1]:
			ans += 1
		else:
			list1.append(ans)
			ans = 1
		if i + 1 == len(y) - 1:
			list1.append(ans)
	list2 = []
	for j in list1:
		if j % 2 != 0:
			list2.append((j + 1) / 2)
		else:
			list2.append(int(j / 2))
	if x > 1:
		print(int(sum(list2)))
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	s = input() + '0'
	l = []
	i = 0
	while i < n:
		if s[i] == s[i + 1]:
			l.append(s[i] + s[i + 1])
			i += 2
		else:
			l.append(s[i])
			i += 1
	print(len(l))


t = int(input())
for i in range(t):
	a = int(input())
	n = input()
	b = 0
	while b < len(n) - 1:
		if n[b] == n[b + 1]:
			b = b + 2
			a = a - 1
		else:
			b = b + 1
	print(a)


test_cases = int(input())
for _ in range(test_cases):
	n = int(input())
	string = input()
	i = 0
	while i < len(string) - 1:
		if string[i] == string[i + 1]:
			n -= 1
			i += 2
		else:
			i += 1
	print(n)


for _ in range(int(input())):
	N = int(input())
	S = input()
	count = 0
	index = 0
	while index < len(S) - 1:
		if S[index] == S[index + 1]:
			index += 2
		else:
			index += 1
		count += 1
	if index == N - 1:
		count += 1
	print(count)


for i in range(int(input())):
	a = int(input())
	s = input()
	i = 0
	u = 0
	while i < a - 1:
		if s[i] == s[i + 1]:
			i += 2
			u += 1
		else:
			i += 1
	print(a - u)


for _ in range(int(input())):
	inpt = int(input())
	arr = list(input())
	g = 0
	count = 0
	for x in range(1, inpt + 1):
		if len(arr) == 0:
			break
		if len(arr) > 1:
			if arr[g] == arr[g + 1]:
				arr.pop(0)
				arr.pop(0)
				count += 1
			else:
				arr.pop(0)
				count += 1
		else:
			arr.pop(0)
			count += 1
	print(count)


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	count = 0
	i = 0
	while i < len(S) - 1:
		if S[i] == S[i + 1]:
			count += 1
			i += 2
		else:
			i += 1
	print(N - count)


for _ in range(int(input())):
	length = int(input())
	s = input()
	count = 0
	b = 0
	for i in range(len(s)):
		if i == 0:
			count += 1
		elif s[i] == s[i - 1]:
			b += 1
			if b % 2 == 0:
				count += 1
		else:
			count += 1
			b = 0
	print(count)


n_ = int(input())
for _ in range(n_):
	n = int(input())
	s = input()
	count = 0
	i = 0
	while i < len(s) - 1:
		if s[i] == s[i + 1]:
			i = i + 2
			n -= 1
		else:
			i += 1
	print(n)


cases = int(input())
for i in range(cases):
	n = int(input())
	a = list(input())
	count = 0
	count2 = 0
	even = False
	k = 0
	while k < len(a) - 1:
		if a[k] == a[k + 1]:
			n -= 1
			k = k + 2
		else:
			k += 1
	print(n)


for _ in range(int(input())):
	n = int(input())
	s = input()
	k = 0
	x = 0
	t = 0
	for i in range(n - 1):
		if s[i] == s[i + 1] and x < 1:
			k = k + 1
			t = t + 1
			x = x + 1
		else:
			x = 0
			k = k + 1
	print(k - t + 1)


for i in range(int(input())):
	m = int(input())
	s = input()
	c = 0
	while c < len(s) - 1:
		if s[c] == s[c + 1]:
			c += 2
			m -= 1
		else:
			c += 1
	print(m)


for T in range(int(input())):
	n = int(input())
	s = input()
	s += ' '
	count = 0
	index = 0
	while index < n:
		if s[index] == s[index + 1]:
			count += 1
			index += 2
		else:
			count += 1
			index += 1
	print(count)


for i in range(int(input())):
	s = int(input())
	n = 0
	word = input()
	while True:
		try:
			if word[0] == word[1]:
				word = word[2:]
			else:
				word = word[1:]
			n += 1
		except:
			if len(word) == 1:
				n += 1
			break
	print(n)


for _ in range(int(input())):
	n = int(input())
	a = input()
	a = list(a)
	c = 0
	i = 0
	while i < len(a) - 1:
		if a[i] == a[i + 1]:
			a.remove(a[i])
		i += 1
	print(len(a))


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	n1 = 0
	while c < len(s) - 1:
		if s[c] != s[c + 1]:
			c = c + 1
		elif s[c] == s[c + 1]:
			c = c + 2
			n1 = n1 + 1
	print(n - n1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(input())
	j = 0
	cnt = 0
	while j < n - 1:
		if l[j] == l[j + 1]:
			j += 2
		else:
			j += 1
		cnt += 1
	if j == n - 1:
		cnt += 1
	print(cnt)


for i in range(int(input())):
	n = int(input())
	s = input()
	(c, i) = (0, 0)
	while i < n:
		if i + 1 < n and s[i] == s[i + 1]:
			c += 1
			i += 1
		else:
			c += 1
		i += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	s = input()
	k = 0
	while k < len(s) - 1:
		if s[k] == s[k + 1]:
			k += 2
			n -= 1
		else:
			k += 1
	print(n)


for i in range(int(input())):
	num = int(input())
	s = input()
	s = list(s)
	s.append('1')
	count = 0
	j = 0
	while j < num:
		if s[j] == s[j + 1]:
			count = count + 1
			j += 1
		else:
			count += 1
		j += 1
	print(count)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	c = 0
	while c < len(s) - 1:
		if s[c] == s[c + 1]:
			c += 2
			n = n - 1
		else:
			c += 1
	print(n)
	t -= 1


t = int(input())
for u in range(t):
	n = int(input())
	s = input().strip()
	x = s[0]
	i = 1
	p = s[0]
	count = 0
	while i < n:
		if x == s[i]:
			p += s[i]
		else:
			count += len(p) // 2 + len(p) % 2
			p = s[i]
		x = s[i]
		i += 1
	count += len(p) // 2 + len(p) % 2
	print(count)


i = int(input())
x = 0
list1 = []
while x < i:
	k = int(input())
	p = input() + '$'
	ii = 0
	tot = 0
	while ii < k:
		if p[ii] == p[ii + 1]:
			tot = tot + 1
			ii = ii + 2
		else:
			tot = tot + 1
			ii = ii + 1
	list1.append(tot)
	x = x + 1
for ele in list1:
	print(ele)


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	s = s + ' '
	p = 0
	c = 0
	while c < n:
		if s[c] == s[c + 1]:
			p += 1
			c += 1
		else:
			p += 1
		c += 1
	print(p)


for i in range(int(input())):
	N = int(input())
	S = input()[:N]
	S = S + ' '
	c = 0
	j = 0
	while j < N:
		if S[j] == S[j + 1]:
			c += 1
			j += 1
		else:
			c += 1
		j += 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	string = input()
	(i, moves) = (0, 0)
	while i <= n - 1:
		if i <= n - 2:
			if string[i] == string[i + 1]:
				moves += 1
				i += 2
			else:
				moves += 1
				i += 1
		else:
			moves += 1
			i += 1
	print(moves)