You have a string $s$ consisting of $n$ characters. Each character is either 0 or 1.

You can perform operations on the string. Each operation consists of two steps:  select an integer $i$ from $1$ to the length of the string $s$, then delete the character $s_i$ (the string length gets reduced by $1$, the indices of characters to the right of the deleted one also get reduced by $1$);  if the string $s$ is not empty, delete the maximum length prefix consisting of the same characters (the indices of the remaining characters and the string length get reduced by the length of the deleted prefix). 

Note that both steps are mandatory in each operation, and their order cannot be changed.

For example, if you have a string $s =$ 111010, the first operation can be one of the following:  select $i = 1$: we'll get 111010 $\rightarrow$ 11010 $\rightarrow$ 010;  select $i = 2$: we'll get 111010 $\rightarrow$ 11010 $\rightarrow$ 010;  select $i = 3$: we'll get 111010 $\rightarrow$ 11010 $\rightarrow$ 010;  select $i = 4$: we'll get 111010 $\rightarrow$ 11110 $\rightarrow$ 0;  select $i = 5$: we'll get 111010 $\rightarrow$ 11100 $\rightarrow$ 00;  select $i = 6$: we'll get 111010 $\rightarrow$ 11101 $\rightarrow$ 01. 

You finish performing operations when the string $s$ becomes empty. What is the maximum number of operations you can perform?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line contains string $s$ of $n$ characters. Each character is either 0 or 1.

It's guaranteed that the total sum of $n$ over test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print a single integer — the maximum number of operations you can perform.


-----Example-----
Input
5
6
111010
1
0
1
1
2
11
6
101010

Output
3
1
1
1
3



-----Note-----

In the first test case, you can, for example, select $i = 2$ and get string 010 after the first operation. After that, you can select $i = 3$ and get string 1. Finally, you can only select $i = 1$ and get empty string.

Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Data structures

Greedy algorithms
Skill types: Data structures

Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
for t in range(int(input())):
	n = int(input())
	s = input()
	if n < 3:
		print(1)
	else:
		a = []
		b = []
		c = 1
		j = 0
		for i in range(1, n):
			if s[i] == s[i - 1]:
				c += 1
			else:
				a.append(c)
				if c > 1:
					b.append(j)
				c = 1
				j += 1
		a.append(c)
		if c > 1:
			b.append(j)
		la = len(a)
		lb = len(b)
		if lb == 0:
			print((la + 1) // 2)
		else:
			ia = ib = r = 0
			while ia < la:
				r += 1
				if a[ia] == 1:
					a[b[ib]] -= 1
					if a[b[ib]] == 1:
						ib += 1
						if ib >= lb:
							r += (la - ia) // 2
							break
				else:
					ib += 1
					if ib >= lb:
						r += (la - ia) // 2
						break
				ia += 1
			print(r)


from sys import stdin, stdout
import math, sys
from itertools import permutations, combinations
from collections import defaultdict, deque, OrderedDict, Counter
from os import path
import bisect as bi
import heapq
mod = 10 ** 9 + 7

def yes():
	print('YES')

def no():
	print('NO')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def inp():
		return int(input())

	def minp():
		return map(int, input().split())
else:

	def inp():
		return int(stdin.readline())

	def minp():
		return map(int, stdin.readline().split())
for _ in range(inp()):
	n = inp()
	a = list(map(int, input()))
	b = []
	count = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			b.append(count)
			count = 1
		else:
			count += 1
	if count > 0:
		b.append(count)
	n = len(b)
	if n == 1:
		print(1)
		continue
	op = 0
	head = 0
	tail = 0
	if b[0] > 1:
		op += 1
		b[head] = 0
		head += 1
		tail += 1
	while head < n:
		if b[head] == 1:
			head += 1
			continue
		if b[head] > 1 and b[head - 1] == 0:
			b[head] = 0
			head += 1
			tail += 1
			op += 1
			continue
		if b[head] > 1:
			b[head] -= 1
			b[tail] -= 1
			tail += 1
			op += 1
			if b[head] == 1:
				head += 1
	print(op + math.ceil(b.count(1) / 2))


import sys
import math
from collections import defaultdict, Counter
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 1
	l = []
	for j in range(1, n):
		if s[j] == s[j - 1]:
			c += 1
		else:
			l.append(c)
			c = 1
	l.append(c)
	l1 = []
	for j in range(len(l)):
		if l[j] > 1:
			l1.append([l[j], j])
	top = 0
	ans = 0
	flag = 0
	for j in range(len(l)):
		if flag == 1:
			flag = 0
			continue
		if l[j] > 1:
			ans += 1
		else:
			ans += 1
			if j == len(l) - 1:
				break
			while top < len(l1) and l1[top][1] <= j:
				top += 1
			if top == len(l1):
				flag = 1
			else:
				l1[top][0] -= 1
				l[l1[top][1]] -= 1
				if l1[top][0] == 1:
					top += 1
	print(ans)


import math

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		count = 1
		ar = []
		for i in range(n - 1):
			if s[i + 1] == s[i]:
				count += 1
			else:
				ar.append(count)
				count = 1
		if count > 0:
			ar.append(count)
		ct = 0
		ans = 0
		for i in ar:
			if i > 1:
				ct = max(0, ct - (i - 2))
				ans += 1
			else:
				ans += 1
				ct += 1
		ans -= int(math.floor(ct / 2))
		print(ans)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for s in range(int(input())):
	n = int(input())
	vals = [int(k) for k in input()]
	chain = [1]
	for s in range(1, n):
		if vals[s] == vals[s - 1]:
			chain[-1] += 1
		else:
			chain.append(1)
	moves = 0
	tracker = []
	for s in range(len(chain)):
		if chain[s] > 1:
			tracker.append([s, chain[s]])
	tracker.reverse()
	nxt = 0
	for s in range(len(chain)):
		while len(tracker) > 0 and tracker[-1][0] < nxt:
			tracker.pop()
		if s >= nxt:
			if len(tracker) > 0:
				if tracker[-1][1] > 1:
					moves += 1
					nxt += 1
					tracker[-1][1] -= 1
				else:
					tracker.pop()
					if len(tracker) > 0:
						moves += 1
						nxt += 1
						tracker[-1][1] -= 1
					else:
						moves += 1
						nxt += 2
			else:
				moves += 1
				nxt += 2
	print(moves)


def prom(a, s):
	ans = 0
	k0 = 0
	k1 = 0
	pred = '2'
	for c in s:
		if c != pred and pred != '2':
			a.append(k0 + k1)
			k0 = 0
			k1 = 0
		if c == '0':
			k0 += 1
		else:
			k1 += 1
		pred = c
	if pred != '2':
		a.append(k0 + k1)
t = int(input())
for ti in range(t):
	n = int(input())
	s = input()
	a = []
	prom(a, s)
	l = len(a)
	bi = 0
	b2 = 0
	ans = 0
	while bi < l:
		for i in range(max(b2, bi), l):
			b2 = i
			if a[i] > 1:
				a[i] -= 1
				bi += 1
				break
		else:
			bi += 2
		ans += 1
	print(ans)


import os
import heapq as h
import sys, threading
import math
import operator
from collections import defaultdict, deque
from io import BytesIO, IOBase
sys.setrecursionlimit(10 ** 5)

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def pw(a, b, md):
	result = 1
	while b > 0:
		if b % 2 == 1:
			result *= a
			result %= md
		a *= a
		a %= md
		b //= 2
	return result % md

def inpt():
	return [int(k) for k in input().split()]

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		count = 1
		ar = []
		for i in range(n - 1):
			if s[i + 1] == s[i]:
				count += 1
			else:
				ar.append(count)
				count = 1
		if count > 0:
			ar.append(count)
		ct = 0
		ans = 0
		for i in ar:
			if i > 1:
				ct = max(0, ct - (i - 2))
				ans += 1
			else:
				ans += 1
				ct += 1
		ans -= int(math.floor(ct / 2))
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
threading.Thread(target=main).start()


import heapq
import collections
from math import log2
import itertools
from functools import lru_cache
from sys import setrecursionlimit as srl
srl(2 * 10 ** 6)
N = 200001

def solve(n, s):
	segs = []
	cur = '?'
	val = 0
	for x in s:
		if x != cur:
			if val:
				segs.append(val)
			val = 1
			cur = x
		else:
			val += 1
	if val:
		segs.append(val)
	total = 0
	debt = 0
	for x in segs:
		total += x - 1
	ans = 0
	kill_nxt = 0
	cnt_nxt = 0
	for x in segs:
		if kill_nxt:
			if cnt_nxt:
				ans += 1
			cnt_nxt = cnt_nxt ^ 1
			continue
		ans += 1
		x -= 1
		if debt < total:
			debt += 1
		else:
			kill_nxt = 1
		debt -= min(debt, x)
		total -= x
	return ans
t = int(input())
for tc in range(1, t + 1):
	n = int(input())
	s = input()
	print(solve(n, s))


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	n = int(sys.stdin.readline().strip())
	s = sys.stdin.readline().strip()
	L = [1]
	for i in range(1, n):
		if s[i] == s[i - 1]:
			L[-1] = L[-1] + 1
		else:
			L.append(1)
	L.reverse()
	i = n - 1
	ans = 0
	while len(L) > 0:
		ans = ans + 1
		v = True
		i = min(i, len(L) - 1)
		while i >= 0 and v == True:
			if L[i] == 1:
				i = i - 1
				if i == -1:
					v = False
			else:
				v = False
		if i == -1:
			L.pop()
		else:
			L[i] = L[i] - 1
		if len(L) > 0:
			L.pop()
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	curr = 1
	a = []
	for i in range(1, n):
		if s[i] != s[i - 1]:
			a.append(curr)
			curr = 1
		else:
			curr += 1
	a.append(curr)
	l = 0
	r = l
	ans = 0
	while l < len(a):
		if a[l] == 0:
			l += 1
			continue
		if a[l] > 1:
			ans += 1
			a[l] = 0
		else:
			while r < len(a) and a[r] <= 1:
				r += 1
			if l < r < len(a):
				a[r] -= 1
				a[l] = 0
				ans += 1
			else:
				ans += (len(a) - l) // 2 + (len(a) - l) % 2
				break
		l += 1
	print(ans)


t = int(input())
for i in range(t):
	ls = int(input())
	s = input()
	c = 0
	l = []
	cnt = 1
	for j in range(1, ls):
		if s[j] == s[j - 1]:
			cnt += 1
		else:
			l.append(cnt)
			cnt = 1
	l.append(cnt)
	j = 0
	while j < len(l) and l[j] == 1:
		j += 1
	ans = 0
	for x in range(len(l)):
		if j == len(l):
			ans += (len(l) - x + 1) // 2
			break
		else:
			l[j] -= 1
			ans += 1
			if l[j] == 1 or j == x:
				j = max(j + 1, x + 1)
				while j < len(l) and l[j] == 1:
					j += 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase
from collections import deque
from math import ceil

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		prefix = [1] * n
		revPrefix = [1] * n
		for i in range(1, n):
			if s[i] == s[i - 1]:
				prefix[i] = 1 + prefix[i - 1]
		for i in range(n - 2, -1, -1):
			if s[i] == s[i + 1]:
				revPrefix[i] = 1 + revPrefix[i + 1]
		modified = list()
		bank = deque()
		steps = 0
		pos = 0
		for i in range(n):
			if prefix[i] == 1:
				extras = max(0, revPrefix[i] - 2)
				if extras > 0:
					bank.append([pos, extras])
				if revPrefix[i] > 1:
					number = 2
				else:
					number = 1
				for _ in range(number):
					modified.append(int(s[i]))
				pos += number
		revPrefix = [1] * pos
		for i in range(pos - 2, -1, -1):
			if modified[i] == modified[i + 1]:
				revPrefix[i] = 1 + revPrefix[i + 1]
		i = 0
		while i < pos:
			if len(bank) == 0:
				steps += ceil((pos - i) / 2)
				break
			steps += 1
			if revPrefix[i] > 1:
				if bank[0][0] == i:
					_ = bank.popleft()
				i += 2
			else:
				bank[0][1] -= 1
				if bank[0][1] == 0:
					_ = bank.popleft()
				i += 1
		print(steps)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = lambda s: self.buffer.write(s.encode()) if self.writable else None

	def read(self):
		if self.buffer.tell():
			return self.buffer.read().decode('ascii')
		return os.read(self._fd, os.fstat(self._fd).st_size).decode('ascii')

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline().decode('ascii')

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

def print(*args, sep=' ', end='\n', file=sys.stdout, flush=False):
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(end)
	if flush:
		file.flush()
(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(10000)
main()


for _ in ' ' * int(input()):
	a = int(input())
	z = [len(i) for i in input().replace('10', '1 0').replace('01', '0 1').split()] + [0]
	ans = 0
	i = 0
	j = len(z) - 1
	f = 0
	while i < j:
		f = max(f, i)
		if z[i] > 1:
			i += 1
		else:
			while f < j and z[f] == 1:
				f += 1
			if z[f] > 1:
				z[f] -= 1
				i += 1
			else:
				i += 2
		ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	si = []
	mi = []
	deleted = set()
	prev = 'a'
	for i in range(n - 1, -1, -1):
		c = s[i]
		if c == prev:
			mi.append(i)
		else:
			si.append(i)
		prev = c
	mi.reverse()
	si.reverse()
	midx = 0
	sidx = 0
	opCnts = 0
	i = 0
	while i < n:
		while midx < len(mi) and mi[midx] < i:
			midx += 1
		if midx < len(mi):
			deleted.add(mi[midx])
			midx += 1
		else:
			while sidx < len(si) and si[sidx] in deleted:
				sidx += 1
			deleted.add(si[sidx])
			sidx += 1
		while i < n and (i in deleted or (i + 1 < n and s[i] == s[i + 1])):
			i += 1
		deleted.add(i)
		i += 1
		opCnts += 1
	print(opCnts)


import sys, os
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))
from time import time
MOD = 998244353

def main():
	ans = []
	for _ in range(int(input())):
		n = int(input())
		s = [len(i) for i in input().strip().replace('10', '1 0').replace('01', '0 1').split(' ')]
		i = j = 0
		m = len(s)
		turns = 0
		while i < m:
			if s[i] == 0:
				i += 1
				continue
			else:
				while j < m and s[j] <= 1:
					j += 1
				if j != m:
					s[j] -= 1
				elif i != m - 1:
					s[i + 1] -= 1
			s[i] = 0
			i += 1
			turns += 1
		ans.append(str(turns))
	print('\n'.join(ans))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(RL())

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def toord(c):
	return ord(c) - ord('a')

def lcm(a, b):
	return a * b // gcd(a, b)
mod = 998244353
INF = float('inf')
from math import factorial, sqrt, ceil, floor, gcd
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush
from itertools import groupby

def main():
	for _ in range(N()):
		n = N()
		s = input()
		arr = [len(list(j)) for (i, j) in groupby(s)]
		res = 0
		n = len(arr)
		i = 0
		pre = 0
		while i < n:
			if arr[i] > 1:
				res += 1
				i += 1
				pre = max(pre, i)
			else:
				for j in range(pre, n):
					if arr[j] > 1:
						arr[j] -= 1
						res += 1
						i += 1
						pre = j
						break
					pre = max(pre, j)
				else:
					i += 2
					res += 1
			pre = max(pre, i)
		print(res)
main()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	list = []
	count = 1
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			count += 1
		else:
			list.append(count)
			count = 1
	list.append(count)
	count = 0
	x = 0
	for i in range(len(list)):
		if x == i and list[i] > 1:
			count += 1
			x += 1
		elif x != i and list[i] > 1:
			while list[i] != 1:
				list[i] -= 1
				x += 1
				count += 1
				if x == i and list[i] > 1:
					count += 1
					x += 1
					break
	count = count + math.ceil((len(list) - x) / 2)
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	l = []
	counter = 1
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			counter += 1
		else:
			l.append(counter)
			counter = 1
	if counter != 0:
		l.append(counter)
	ans = 0
	x = []
	for i in range(len(l) - 1, -1, -1):
		if l[i] > 1:
			x.append([i, l[i]])
	for i in range(len(l)):
		if l[i] > 1:
			ans += 1
			x.pop()
		elif len(x) > 0:
			x[-1][1] -= 1
			l[x[-1][0]] -= 1
			if x[-1][1] == 1:
				x.pop()
			ans += 1
		else:
			ans += (len(l) - i + 1) // 2
			break
	print(ans)


import math
test = int(input())
for _ in range(test):
	n = int(input())
	arr = list(input())
	prefix = [1]
	s = arr[0]
	for i in range(1, n):
		if arr[i] == s:
			prefix[-1] += 1
		else:
			prefix.append(1)
			s = arr[i]
	extra = 0
	for i in range(len(prefix) - 1, -1, -1):
		if prefix[i] >= 2:
			extra += prefix[i] - 2
			prefix[i] = 2
		elif extra:
			prefix[i] += 1
			extra -= 1
	ans = 0
	one = 0
	for i in range(len(prefix)):
		if prefix[i] >= 2:
			ans += 1
		else:
			one += 1
	ans += math.ceil(one / 2)
	print(ans)


import sys
import bisect as bi
import math as mt
import collections as cc
I = lambda : list(map(int, input().split()))
for tc in range(int(input())):
	(n,) = I()
	s = list(input())
	ar = []
	t = s[0]
	cnt = 1
	for i in range(1, n):
		if s[i] == t:
			cnt += 1
		else:
			ar.append(cnt)
			t = s[i]
			cnt = 1
	if cnt:
		ar.append(cnt)
	ans = 0
	nn = len(ar)
	temp = -1
	for i in range(nn):
		if ar[i] > 1:
			temp = i
			break
	for i in range(nn):
		now = ar[i]
		if temp == -1:
			ans += (nn - i + 1) // 2
			break
		elif i == temp:
			ans += 1
			temp += 1
			while temp < nn and ar[temp] == 1:
				temp += 1
		else:
			ans += 1
			ar[temp] -= 1
			if ar[temp] == 1:
				temp += 1
				while temp < nn and ar[temp] == 1:
					temp += 1
		if temp == nn:
			temp = -1
	print(ans)


import sys
import math, bisect
sys.setrecursionlimit(10 ** 6)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict

def I():
	return int(sys.stdin.readline())

def neo():
	return map(int, sys.stdin.readline().split())

def Neo():
	return list(map(int, sys.stdin.readline().split()))
for _ in range(I()):
	n = I()
	s = input()
	l = [len(list(j)) for (_, j) in groupby(list(s))]
	(curr, Ans) = (0, 0)
	for i in range(len(l)):
		curr = min(curr + l[i] - 1, i + 1)
	Ans = curr + (len(l) - curr + 1) // 2
	print(Ans)


import sys
from collections import deque
t = int(input())
import random
input = sys.stdin.readline

def rand_key(p):
	key1 = ''
	for i in range(p):
		temp = str(random.randint(0, 1))
		key1 += temp
	return key1
for _ in range(t):
	n = int(input())
	a = input()
	curr = 1
	prev = a[0]
	segs = []
	for i in range(1, n):
		if a[i] == a[i - 1]:
			curr += 1
		else:
			segs.append(curr)
			curr = 1
		prev = a[i]
	segs.append(curr)
	big_segs = deque()
	for i in range(0, len(segs)):
		if segs[i] > 1:
			big_segs.append((i, segs[i]))
	total = 0
	i = 0
	while i < len(segs) and len(big_segs) >= 1:
		if i == big_segs[0][0]:
			big_segs.popleft()
			i += 1
			total += 1
		else:
			big_segs[0] = (big_segs[0][0], big_segs[0][1] - 1)
			if big_segs[0][1] <= 1:
				big_segs.popleft()
			i += 1
			total += 1
	total += (len(segs[i:]) + 1) // 2
	print(total)


for _ in range(int(input())):
	siz = int(input())
	st = input()
	diff = 0
	q = []
	for x in range(1, siz):
		if st[x] != st[x - 1]:
			diff += 1
		if st[x] == st[x - 1]:
			q.append(diff)
	q.reverse()
	(rem, ans) = (0, 0)
	for x in range(siz):
		if not q:
			break
		q.pop(-1)
		rem += 1
		ans += 1
		while q and q[-1] == x:
			q.pop(-1)
			rem += 1
		rem += 1
	print(ans + (siz - rem + 1) // 2)


t = int(input())
while t:
	n = int(input())
	s = input()
	arr = []
	pb = arr.append
	(cnt, last) = (1, s[0])
	for i in range(1, n):
		if last == s[i]:
			cnt += 1
		else:
			pb(cnt)
			cnt = 1
			last = s[i]
	pb(cnt)
	(i, j, ans) = (0, 0, 0)
	n = len(arr)
	while i < n:
		while j < n and (j <= i or arr[j] == 1):
			j += 1
		ans += 1
		if arr[i] == 1:
			if j < n:
				arr[j] -= 1
			else:
				i += 1
		i += 1
	print(ans)
	t -= 1


import math
t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	count = [0]
	curr = []
	prev = st[-1]
	c = 1
	for s in st[:-1][::-1]:
		if s == prev:
			c += 1
		elif s != prev:
			count.append(c - 1 + count[-1])
			curr.append(c)
			c = 1
			prev = s
	count.append(c - 1 + count[-1])
	curr.append(c)
	ans = 0
	used = 0
	curr = curr[::-1]
	for (index, c) in enumerate(count[1:][::-1]):
		temp = 0
		if used > 0 and curr[index] > 1:
			temp = min(curr[index] - 1, used)
			curr[index] -= temp
			used -= temp
		if curr[index] > 1:
			ans += 1
		elif c - temp - used > 0:
			ans += 1
			used += 1
		else:
			break
	else:
		print(ans)
		continue
	ans += math.ceil((len(count) - 1 - index) / 2)
	print(ans)


def find_next_index(s):
	for pos in range(1, len(s)):
		if s[pos] == s[pos - 1]:
			return pos
	return len(s) - 1

def get_prefix_len(s):
	assert len(s) > 0
	if len(s) == 1:
		return 1
	pos = 1
	while pos < len(s) and s[pos] == s[0]:
		pos += 1
	return pos

def count_max_actions_old(s):
	count = 0
	while len(s) > 0:
		count += 1
		j = find_next_index(s)
		s = s[0:j] + s[j + 1:]
		if len(s) == 0:
			break
		prefix_len = get_prefix_len(s)
		s = s[prefix_len:]
	return count

def find_next_index_rle(i0, max_i, rle):
	for i in range(i0, max_i + 1):
		if rle[i] > 1:
			return i
	return max_i

def get_rle(s):
	assert len(s) > 0
	if len(s) == 1:
		return [1]
	rle = []
	prev_pos = 0
	pos = 1
	while pos < len(s):
		if s[pos] != s[prev_pos]:
			rle.append(pos - prev_pos)
			prev_pos = pos
		pos += 1
	rle.append(pos - prev_pos)
	return rle

def count_max_actions(s):
	count = 0
	rle = get_rle(s)
	start_index = 0
	end_index = len(rle) - 1
	dec_index = 0
	while end_index >= start_index:
		count += 1
		dec_index = find_next_index_rle(dec_index, end_index, rle)
		rle[dec_index] -= 1
		if rle[dec_index] == 0:
			end_index = end_index - 1
			dec_index -= 1
		if end_index < start_index:
			break
		start_index += 1
		if dec_index < start_index:
			dec_index = start_index
	return count
n = int(input())
for t in range(n):
	m = int(input())
	s = input()
	assert len(s) == m
	result = count_max_actions(s)
	print(result)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import time
start_time = time.time()
import collections as col
import math
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def solve():
	N = getInt()
	S = [int(s) for s in input()]
	if N == 1:
		return 1
	prefix = col.deque([])
	curr = 1
	ans = 0
	for j in range(1, N):
		if S[j] == S[j - 1]:
			curr += 1
		else:
			prefix.append(curr)
			curr = 1
		if j == N - 1:
			prefix.append(curr)
	one = 0
	for i in range(len(prefix)):
		p = prefix[i]
		if p == 1:
			one += 1
		elif p - 2 >= one:
			ans += one + 1
			one = 0
		else:
			ans += p - 1
			one -= p - 2
	if one % 2 == 0:
		ans += one // 2
	else:
		ans += one // 2 + 1
	return ans
for _ in range(getInt()):
	print(solve())


from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(t,) = gil()
for _ in range(t):
	(n,) = gil()
	a = g()
	b = [1]
	prev = a[0]
	for i in range(1, n):
		if a[i] == prev:
			b[-1] += 1
		else:
			prev = a[i]
			b.append(1)
	h = []
	m = len(b)
	for i in range(m):
		if b[i] - 1:
			h.append((i, b[i]))
	heapify(h)
	ans = 0
	for i in range(m):
		if i >= len(b):
			break
		if b[i] == 1:
			while h and (h[0][0] <= i or h[0][0] >= len(b) or b[h[0][0]] != h[0][1]):
				heappop(h)
			if h:
				(idx, _) = heappop(h)
				b[idx] -= 1
				if b[idx] > 1:
					heappush(h, (idx, b[idx]))
			else:
				b[-1] -= 1
				if b[-1] == 0:
					b.pop()
				elif b[-1] > 1:
					heappush(h, (len(b) - 1, b[-1]))
		ans += 1
	print(ans)


for t in range(int(input())):
	n = int(input())
	s = input()
	dp = [0 for i in range(n)]
	temp = s[0]
	j = cnt = 0
	i = 1
	if n == 1:
		cnt = 1
	while i < n:
		while i < n and dp[i]:
			i += 1
		if i >= n:
			cnt += 1
			break
		if s[i] == temp:
			i += 1
			while i < n and dp[i]:
				i += 1
			while i < n and (s[i] == temp or dp[i]):
				i += 1
		else:
			while 1:
				if j < i:
					j = i
				while j < n and dp[j]:
					j += 1
				k = j + 1
				while k < n and dp[k]:
					k += 1
				if j >= n or k >= n:
					i = i + 1
					break
				t1 = s[j]
				t2 = s[k]
				if t1 == t2:
					dp[j] = 1
					j = k
					break
				j += 1
		while i < n and dp[i]:
			i += 1
		if i < n:
			temp = s[i]
			dp[i] = 1
		cnt += 1
	print(cnt)


from collections import deque

def read_int() -> int:
	return int(input())

def read_ints():
	return map(int, input().split(' '))

def test_case():
	_ = read_int()
	input_string = input()
	cnt = 0
	sizes_queue = deque()
	prev = None
	for cur in input_string:
		if prev == cur:
			cnt += 1
		else:
			if prev is not None:
				sizes_queue.append(cnt)
			cnt = 1
		prev = cur
	sizes_queue.append(cnt)
	bigger_than_two = deque()
	for (ind, elem) in enumerate(sizes_queue):
		if elem > 1:
			bigger_than_two.append([ind, elem])
	removed = 0
	turns = 0
	while sizes_queue:
		while bigger_than_two:
			(original_index, amount) = bigger_than_two[0]
			current_index = original_index - removed
			if current_index >= 0:
				new_amount = amount - 1
				if new_amount <= 1:
					bigger_than_two.popleft()
					sizes_queue[current_index] -= 1
					break
				else:
					bigger_than_two[0][1] -= 1
					sizes_queue[current_index] -= 1
					break
			else:
				bigger_than_two.popleft()
		else:
			sizes_queue.popleft()
			removed += 1
		if sizes_queue:
			sizes_queue.popleft()
			removed += 1
		turns += 1
	print(turns)
for _ in range(read_int()):
	test_case()


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import *
getcontext().prec = 25
from itertools import permutations
MOD = pow(10, 9) + 7
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	l = input()
	a = [1]
	for i in range(1, n):
		if l[i] == l[i - 1]:
			a[-1] += 1
		else:
			a.append(1)
	extra = [0] * len(a)
	for i in range(1, len(a)):
		extra[i] = extra[i - 1] + max(0, a[i] - 2)
	i = 0
	c = 0
	j = 1
	x = len(a)
	while i < x:
		if i == j:
			j += 1
		if a[i] >= 2:
			c += 1
			i += 1
			if i == j:
				j += 1
		elif a[i] == 1:
			check = False
			if j < x:
				while j < x:
					if a[j] >= 2:
						check = True
						break
					j += 1
			if check:
				a[j] -= 1
				i += 1
				c += 1
			else:
				c += 1
				i += 2
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	arr = input()
	delcnt = 1
	actual = 0
	for j in range(0, n - 1):
		if arr[j] == arr[j + 1]:
			if delcnt:
				actual += 1
				delcnt -= 1
		else:
			delcnt += 1
	if delcnt % 2:
		actual += delcnt // 2 + 1
	else:
		actual += delcnt // 2
	print(actual)


for _ in range(int(input())):
	n = int(input())
	s = input()
	blocks = []
	size = 1
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			size += 1
		else:
			blocks.append(size)
			size = 1
	blocks.append(size)
	lost = 0
	free_moves = 0
	for block_size in blocks:
		if block_size > 2:
			free_moves_used = min(free_moves, block_size - 2)
			free_moves -= free_moves_used
			lost += block_size - 2 - free_moves_used
		elif block_size == 1:
			free_moves += 1
	l = n - lost
	print(l // 2 + l % 2)


cases = int(input())
for t in range(cases):
	n = int(input())
	s = input() + '!'
	c = []
	v = 1
	l = 0
	for i in range(1, n + 1):
		if s[i] == s[i - 1]:
			v += 1
		else:
			c.append(v)
			l += 1
			v = 1
	(i, out, dl) = (0, 0, 0)
	while i < l:
		out += 1
		while dl < l and c[dl] <= 1:
			dl += 1
		if dl < l and c[dl] > 1:
			c[dl] -= 1
		else:
			i += 1
		i += 1
		dl = max(i, dl)
	print(out)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	cnt = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			ans += 1
			ans = min(ans, cnt)
		else:
			cnt += 1
	ans += (cnt - ans + 1) // 2
	print(ans)


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint

def main():
	n = int(input())
	s = [c for c in input()]
	s.reverse()
	cnt = 0
	bor = 0
	while len(s):
		prev = s[-1]
		cnt += 1
		k = 0
		while len(s) and s[-1] == prev:
			k += 1
			s.pop()
		if k > 0:
			bor -= min(bor, k - 2)
			continue
		else:
			bor += 1
	ans = cnt - bor // 2
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	main()


import sys, math, bisect
inf = float('inf')
mod = inf + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def freq(a, x):
	z = upperBound(a, x) - lowerBound(a, x)
	if z <= 0:
		return 0
	return z
from collections import deque
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	c = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			ans += 1
			ans = min(ans, c)
		else:
			c += 1
	print(ans + (c - ans + 1) // 2)


from collections import Counter
import string
import math
import sys

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
for _ in range(vary(1)):
	n = vary(1)
	s = '&' + input()
	count = 0
	i = 0
	num = 0
	q = 0
	if n == 1:
		print(1)
		continue
	for i in range(1, n + 1):
		if s[i] != s[i - 1]:
			num += 1
			q += 1
		elif q > 0:
			q -= 1
		if q >= n - i:
			break
	print(num)


import sys as _sys
ZERO = '0'
ONE = '1'

def main():
	t = int(input())
	for i_t in range(t):
		(n,) = _read_ints()
		s = _read_line()
		result = find_max_operations_n_can_make(s)
		print(result)

def _read_line():
	result = _sys.stdin.readline()
	assert result[-1] == '\n'
	return result[:-1]

def _read_ints():
	return map(int, _read_line().split())

def find_max_operations_n_can_make(s):
	assert isinstance(s, str)
	islands_lengths = []
	curr_length = 1
	for (prev_x, curr_x) in zip(s, s[1:]):
		if curr_x == prev_x:
			curr_length += 1
		else:
			islands_lengths.append(curr_length)
			curr_length = 1
	islands_lengths.append(curr_length)
	islands_n = len(islands_lengths)
	islands_powers = [length - 1 for length in islands_lengths]
	indexed_nonzero_islands_powers_rev = [[i, power] for (i, power) in enumerate(islands_powers) if power != 0][::-1]
	i_next_island_to_eat = 0
	while indexed_nonzero_islands_powers_rev:
		indexed_nonzero_islands_powers_rev[-1][1] -= 1
		if indexed_nonzero_islands_powers_rev[-1][1] == 0:
			indexed_nonzero_islands_powers_rev.pop()
		while indexed_nonzero_islands_powers_rev and indexed_nonzero_islands_powers_rev[-1][0] <= i_next_island_to_eat:
			indexed_nonzero_islands_powers_rev.pop()
		i_next_island_to_eat += 1
	islands_eaten = i_next_island_to_eat
	assert islands_eaten <= islands_n
	one_elem_islands_remain = islands_n - islands_eaten
	moves_used = islands_eaten
	moves_used += one_elem_islands_remain // 2 + one_elem_islands_remain % 2
	return moves_used
main()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	arr = []
	val = s[0]
	c = 0
	for i in s:
		if i == val:
			c += 1
		else:
			arr.append(c)
			c = 1
			val = i
	if c > 0:
		arr.append(c)
	ans = 0
	q = []
	for i in range(len(arr)):
		if arr[i] != 1:
			q.append(i)
	k = 0
	while 1:
		if arr == []:
			break
		if arr[0] > 1:
			ans += 1
			q.pop(0)
			arr.pop(0)
		else:
			if len(q) > 0:
				arr[q[0] - k] -= 1
				if arr[q[0] - k] == 1:
					q.pop(0)
				ans += 1
			else:
				ans += len(arr) // 2 + len(arr) % 2
				break
			arr.pop(0)
		k += 1
	print(ans)


n = int(input())
for _ in range(n):
	k = int(input())
	s = input()
	s = s[0] + s + str(int(s[-1]) ^ 1)
	m = []
	prev = 1
	for i in range(1, k + 2):
		if s[i] != s[i - 1]:
			m.append(i - prev)
			prev = i
	ans = 0
	start = 0
	end = len(m)
	first = 0
	while start < end:
		if m[start] > 1:
			start += 1
			first = max(first, start)
		else:
			while first < end and m[first] == 1:
				first += 1
			if first >= end:
				end -= 1
			else:
				m[first] -= 1
			start += 1
		ans += 1
	print(ans)


import math
t = int(input())

def get_non_singleton_block_ind(blocks, start_ind, block_amount):
	for j in range(start_ind, block_amount):
		if blocks[j] > 1:
			return j
	return block_amount

def get_repeat_string_blocks(s):
	blocks = []
	prev_item = ''
	for i in range(0, len(s)):
		if s[i] != prev_item:
			blocks.append(1)
			prev_item = s[i]
		else:
			blocks[len(blocks) - 1] += 1
	return blocks
for case in range(0, t):
	n = int(input())
	s = list(input())
	blocks = get_repeat_string_blocks(s)
	max_steps = 0
	blocks_removed = 0
	block_amount = len(blocks)
	non_singleton_block_ind = -1
	for i in range(0, block_amount):
		if non_singleton_block_ind < i or blocks[non_singleton_block_ind] == 1:
			non_singleton_block_ind = get_non_singleton_block_ind(blocks, max(i, non_singleton_block_ind), block_amount)
		if non_singleton_block_ind == block_amount:
			break
		blocks[non_singleton_block_ind] -= 1
		max_steps += 1
		blocks_removed += 1
	blocks_remaining = block_amount - blocks_removed
	max_steps += int(math.ceil(blocks_remaining / float(2)))
	print(max_steps)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = []
	curr = 1
	g = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			curr += 1
		else:
			a.append(curr)
			if curr > 1:
				g += 1
			curr = 1
	if curr > 0:
		if curr > 1:
			g += 1
		a.append(curr)
	j = 0
	i = 0
	res = 0
	while i < len(a):
		if a[i] > 1:
			res += 1
			i += 1
		else:
			j = max(i + 1, j)
			ch = 0
			while j < len(a):
				if a[j] > 1:
					a[j] -= 1
					ch = 1
					break
				j += 1
			if ch == 1:
				i += 1
				res += 1
			else:
				i += 2
				res += 1
	print(res)


from sys import stdin
input = stdin.readline

def p1():
	from collections import deque
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = [bool(int(x)) for x in input().rstrip()]
		l = deque()
		curr = s[0]
		currLength = 1
		for i in range(1, n):
			if s[i] == curr:
				currLength += 1
			else:
				l.append(currLength)
				currLength = 1
				curr = not curr
		l.append(currLength)
		j = 0
		tot = 0
		while len(l) > 0:
			while j < len(l) and l[j] == 1:
				j += 1
			if j < len(l):
				l[j] -= 1
			else:
				l.pop()
				j -= 1
			if len(l) > 0:
				l.popleft()
				if j > 0:
					j -= 1
			tot += 1
		print(tot)
p1()


for u in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	x = 0
	y = 1
	for i in range(1, n):
		if s[i - 1] == s[i]:
			x += 1
			x = min(x, y)
		else:
			y += 1
	ans = x + (y - x + 1) // 2
	print(ans)


import math

def mi():
	return map(int, input().strip().split(' '))
for _ in range(int(input())):
	n = int(input())
	s = input()
	segs = []
	c = 1
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			c += 1
		else:
			segs.append(c)
			c = 1
	segs.append(c)
	l = len(segs)
	ans = 0
	j = 0
	tr = 0
	for i in range(l):
		if tr == 1:
			tr = 0
			continue
		if segs[i] == 1:
			j = max(j, i + 1)
			f = 0
			while j < l:
				if segs[j] > 1:
					segs[j] -= 1
					f = 1
					break
				j += 1
			if f == 0:
				tr = 1
		ans += 1
	print(ans)


def solve(s):
	cur = 0
	i = 0
	last = i
	ans = 0
	power = 0
	while i <= len(s):
		if i == len(s) or s[i] != s[last]:
			while power and cur > 2:
				power -= 1
				cur -= 1
				ans += 1
			if cur == 1:
				ans += 1
				power += 1
			if cur >= 2:
				ans += 2
			cur = 0
			last = i
		cur += 1
		i += 1
	return (ans + 1) // 2
for _ in range(int(input())):
	_ = input()
	s = input()
	print(solve(s))


import math
t = int(input())
for i in range(t):
	n = int(input())
	s = [i for i in input()]
	if len(set(s)) == 1:
		print(1)
	else:
		(first, sec) = (0, 0)
		ans = 0
		while sec < n - 1:
			for i in range(max(sec + 1, first + 1), n):
				if s[i] == s[i - 1]:
					first = i
					break
			else:
				count = 0
				for i in range(n - 1, sec, -1):
					if s[i] == s[i - 1]:
						count += 1
				first = n - 1
				ans += math.ceil((first - sec + 1 - count) / 2)
				break
			for i in range(sec + 1, n):
				if s[i] != s[i - 1]:
					sec = i
					break
			else:
				sec = n - 1
			ans += 1
		if sec == n - 1 and first != n - 1 and (s[sec] != s[first]):
			ans += 1
		print(ans)


import os, sys
from io import BytesIO, IOBase
from heapq import *

class Node:

	def __init__(self, le, ind):
		self.le = le
		self.ind = ind

	def __lt__(self, other):
		if self.le == other.le == 1:
			return self.ind > other.ind
		if self.le == 1:
			return False
		if other.le == 1:
			return True
		return self.ind < other.ind

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input().strip()
		prefix = []
		heapify(prefix)
		pre = []
		(o, z, j) = (0, 0, 1)
		for i in range(n):
			if s[i] == '1':
				o += 1
				if z:
					heappush(prefix, Node(z, j))
					pre.append(Node(z, j))
					j += 1
					z = 0
			else:
				z += 1
				if o:
					heappush(prefix, Node(o, j))
					pre.append(Node(o, j))
					j += 1
					o = 0
		if o:
			heappush(prefix, Node(o, j))
			pre.append(Node(o, j))
		if z:
			heappush(prefix, Node(z, j))
			pre.append(Node(z, j))
		op = 0
		flag = [0] * (2 * 10 ** 5 + 1)
		for (ind, i) in enumerate(pre):
			if not i.le:
				continue
			elif i.le > 1:
				flag[ind + 1] = 1
			else:
				while len(prefix):
					x = heappop(prefix)
					if not flag[x.ind]:
						x.le -= 1
						pre[x.ind - 1].le -= 1
						if x.le:
							heappush(prefix, x)
						break
			op += 1
		print(op)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	pref = [1]
	for i in range(1, n):
		if s[i] == s[i - 1]:
			pref[-1] += 1
		else:
			pref.append(1)
	q = list(reversed(pref))
	res = 0
	k = len(q) - 1
	while q:
		if q[-1] > 1:
			k -= 1
			q.pop()
			res += 1
		else:
			while k >= 0 and q[k] == 1:
				k -= 1
			if k >= 0:
				q[k] -= 1
				q.pop()
				res += 1
			else:
				res += math.ceil(len(q) / 2)
				break
	print(res, flush=True)


T = int(input())
for _ in range(0, T):
	n = int(input())
	s = input()
	many = 0
	c = 1
	tempp = 1
	st = ''
	k1 = 0
	k2 = 0
	for i in range(len(s) - 2, -1, -1):
		if s[i] != s[i + 1]:
			if tempp == 0:
				tempp = 1
				many += c - 1
				k2 += 1
			elif c >= 2:
				many += c - 2
				k1 += 1
			elif many > 0:
				many -= 1
				k1 += 1
			else:
				k2 += 1
			c = 1
		else:
			c += 1
	if c >= 2:
		many += c - 2
		k1 += 1
	elif many > 0:
		many -= 1
		k1 += 1
	else:
		k2 += 1
	ans = k1 + k2 // 2
	if k2 % 2 != 0:
		ans += 1
	print(ans)


t = int(input())
for case in range(t):
	n = int(input())
	s = input()
	i = 0
	x = []
	while i < n:
		cnt = 1
		while i + cnt < n and s[i + cnt] == s[i]:
			cnt += 1
		x.append(cnt)
		i += cnt
	i = 0
	j = 0
	ops = 0
	while x:
		f = False
		while i < len(x):
			if x[i] > 1:
				x[i] -= 1
				ops += 1
				f = True
				break
			else:
				i += 1
		if not f:
			del x[-1]
			ops += 1
		if len(x) > 0:
			del x[0]
		i = max(i - 1, 0)
	print(ops)


from sys import stdin, stdout
from bisect import bisect_left
st = lambda : list(stdin.readline().strip())
li = lambda : list(map(int, stdin.readline().split()))
mp = lambda : map(int, stdin.readline().split())
inp = lambda : int(stdin.readline())
pr = lambda n: stdout.write(str(n) + '\n')
mod = 1000000007
INF = float('inf')

def solve():
	n = inp()
	x = [1]
	s = st()
	i = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			x[-1] += 1
		else:
			x.append(1)
	ans = len(x)
	i = 0
	j = 0
	l = len(x)
	while i < l:
		while j < len(x) and x[j] == 1:
			j += 1
		if j < len(x):
			x[j] -= 1
		else:
			l -= 1
			l = max(i + 1, l)
		i += 1
		j = max(i, j)
	ans -= len(x) - l
	pr(ans)
for _ in range(inp()):
	solve()


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	for _ in range(int(input())):
		N = int(input())
		S = input().rstrip('\n')
		S = [int(s) for s in S[::-1]]
		A = []
		prev = S[0]
		cnt = 0
		for s in S:
			if s == prev:
				cnt += 1
			else:
				A.append(cnt)
				cnt = 1
				prev ^= 1
		A.append(cnt)
		ans = 0
		i = len(A) - 1
		while A:
			ans += 1
			if i >= 0:
				while True:
					if A[i] > 1:
						A[i] -= 1
						break
					else:
						i -= 1
						if i < 0:
							A.pop()
							break
			else:
				A.pop()
			if A:
				A.pop()
				if i == len(A):
					i -= 1
		print(ans)
main()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	string = []
	flag = False
	temp = ''
	stack = []
	for i in range(n):
		if not stack:
			stack.append(s[i])
		elif s[i] == stack[-1]:
			stack.append(s[i])
		else:
			string.append(len(stack))
			stack = [s[i]]
	if stack:
		string.append(len(stack))
	i = 0
	j = 0
	c = 0
	n = len(string)
	flag = False
	while i < n:
		if not flag:
			if string[j] >= 2:
				if i == j:
					string[j] = 0
				else:
					string[j] -= 1
				i += 1
				c += 1
			else:
				j += 1
			if j == n:
				flag = True
		else:
			a = n - 1 - i + 1
			c += a // 2
			if a % 2 != 0:
				c += 1
			break
	print(c)


def solve(n, s):
	last = s[0]
	cur = 1
	patch = []
	for c in s[1:]:
		if c == last:
			cur += 1
		else:
			patch.append(cur)
			cur = 1
		last = c
	patch.append(cur)
	lp = len(patch)
	ans = 0
	j = 0
	while j < lp and patch[j] == 1:
		j += 1
	for i in range(lp):
		if j < lp:
			patch[j] -= 1
			ans += 2
		else:
			ans += 1
		j = max(j, i + 1)
		while j < lp and patch[j] == 1:
			j += 1
	print(ans // 2 + ans % 2)
T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	solve(n, s)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	rd = 0
	id = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			rd = min(rd + 1, id)
		else:
			id += 1
	print(rd + (id - rd + 1) // 2)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	st = 0
	i = n - 1
	ans = 0
	while i >= 0:
		size = 0
		de = s[i]
		while i >= 0 and s[i] == de:
			size += 1
			i -= 1
		st += size - 1
		ans += 1
		if st == 0 and i == -1:
			break
		if st == 0:
			i -= 1
		else:
			st -= 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	conts = []
	last = None
	for c in s:
		if c == last:
			conts[-1] += 1
		else:
			conts.append(1)
			last = c
	before = 0
	ops = 0
	for (i, cont) in enumerate(conts):
		before += 1
		if cont > 1:
			_ops = min(before, cont - 1)
			before -= _ops
			ops += _ops
	print(ops + (before + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	k = 0
	l = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			k += 1
			k = min(k, l)
		else:
			l += 1
	k += (l - k + 1) // 2
	print(k)


for i in range(int(input())):
	n = int(input())
	s = input()
	arr = []
	curr = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			curr += 1
		else:
			arr.append(curr)
			curr = 1
	arr.append(curr)
	i = 0
	j = 0
	steps = 0
	while i < len(arr):
		if arr[i] == 1:
			while j < len(arr) and arr[j] == 1:
				j += 1
			if j < len(arr):
				arr[j] -= 1
				i += 1
			else:
				steps += (len(arr) - i) // 2 + (len(arr) - i) % 2
				break
		else:
			i += 1
			if j < i:
				j = i
		steps += 1
	print(steps)


for _ in range(int(input())):
	n = int(input())
	(pref, last) = ([], '')
	for i in input():
		if i != last:
			pref.append(1)
			last = i
		else:
			pref[-1] += 1
	ans = 0
	(i, curr) = (0, 0)
	while i < len(pref):
		curr = max(curr, i)
		if pref[i] < 2:
			while curr < len(pref) - 1 and pref[curr] == 1:
				curr += 1
			if pref[curr] < 2:
				i += 1
			else:
				pref[curr] -= 1
		i += 1
		ans += 1
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = str(input())
	turn_ost = 0
	cnt = 0
	turn = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			turn_ost = min(turn, turn_ost + cnt)
			cnt = 0
			turn += 1
		else:
			cnt += 1
	turn_ost = min(turn, turn_ost + cnt)
	print(math.ceil((turn + turn_ost) / 2))


from sys import stdin, stdout
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	s = stdin.readline()
	s1 = []
	i = 0
	ind = []
	while i < n:
		j = i + 1
		while j < n and s[j] == s[i]:
			j += 1
		s1.append([int(s[i]), j - i])
		if j - i >= 3:
			ind.append(len(s1) - 1)
		i = j
	op = 0
	for i in range(len(s1)):
		if s1[i][1] == 0:
			continue
		if s1[i][1] == 1:
			op += 1
			while len(ind) != 0 and ind[0] < i:
				ind.pop(0)
			if len(ind) != 0:
				s1[ind[0]][1] -= 1
				if s1[ind[0]][1] == 2:
					ind.pop(0)
			elif i + 1 < len(s1):
				s1[i + 1][1] -= 1
		else:
			op += 1
	print(op)


for _ in range(int(input())):
	n = int(input())
	s = input()
	blocks = [[s[0], 1]]
	for i in range(1, n):
		if s[i] == blocks[-1][0]:
			blocks[-1][1] += 1
		else:
			blocks += [[s[i], 1]]
	ind = -1
	for i in range(n):
		if blocks[i][1] > 1:
			ind = i
			break
	ans = 0
	for i in range(len(blocks)):
		if ind == -1:
			break
		ans += 1
		blocks[ind][1] -= 1
		blocks[i][1] = 0
		while ind < len(blocks) and blocks[ind][1] <= 1:
			ind += 1
		if ind == len(blocks):
			ind = -1
	cnt = 0
	for i in range(len(blocks)):
		cnt += blocks[i][1]
	ans += (cnt + cnt % 2) // 2
	print(ans)


ts = int(input())
for t in range(ts):
	n = int(input())
	l = input()
	a = []
	curr = l[0]
	count = 1
	for i in l[1:]:
		if i == curr:
			count += 1
		else:
			a.append(count)
			count = 1
			curr = i
	a.append(count)
	p1 = 0
	p2 = 0
	op = 0
	la = len(a)
	while p1 < la and a[p1] == 1:
		p1 += 1
	while p1 < la and p2 < la:
		a[p1] -= 1
		p2 += 1
		op += 1
		if p1 < p2:
			p1 += 1
		while p1 < la and a[p1] == 1:
			p1 += 1
	if p1 == la:
		if (la - p2) % 2:
			op += (la - p2) // 2 + 1
		else:
			op += (la - p2) // 2
	print(op)


import heapq
for _ in range(int(input())):
	n = int(input())
	s = input()
	st = []
	arr = []
	(l, r) = (0, 0)
	while l < n:
		r = l
		while r + 1 < n and s[r + 1] == s[l]:
			r += 1
		st.append(l)
		if r - l + 1 > 1:
			arr.append([l, r - l + 1])
		l = r + 1
	st = st[-1::-1]
	ans = 0
	heapq.heapify(arr)
	while st != []:
		x = st.pop()
		if len(arr) == 0:
			ans += 1
			if st != []:
				st.pop()
		else:
			cur = heapq.heappop(arr)
			if cur[0] == x:
				ans += 1
			else:
				ans += 1
				cur[1] -= 1
				if cur[1] > 1:
					heapq.heappush(arr, cur)
	print(ans)


from collections import deque

def p(a):
	l = []
	for i in range(len(a)):
		if i <= len(a) - 2 and a[i] == a[i + 1]:
			l.append(i)
	return deque(l)

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(input())
		(d, de, s, ans) = (p(a), 0, set(), 0)
		(i, j) = (0, 0)
		while i < n:
			while d and d[0] < i:
				d.popleft()
			if not d:
				break
			while i in s:
				i += 1
			ans += 1
			x = d.popleft()
			s.add(x)
			t = i + 1
			while t < n and a[i] == a[t]:
				t += 1
			i = t
		de = 0
		for j in range(i, n):
			if j not in s:
				de += 1
		print(ans + de // 2 + de % 2)
main()


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	groups = []
	last = ''
	cnt = 0
	for c in s:
		if c != last:
			if cnt:
				groups.append(cnt)
			cnt = 1
		else:
			cnt += 1
		last = c
	if cnt:
		groups.append(cnt)
	m = len(groups)
	i = 0
	j = 0
	ops = 0
	while i < m:
		ops += 1
		while j < i or (j < m and groups[j] == 1):
			j += 1
		if j < m:
			groups[j] -= 1
		else:
			i += 1
		i += 1
	print(ops)


import sys
read = lambda : sys.stdin.readline().strip()
readi = lambda : map(int, read().split())
from collections import *
from math import *
for _ in range(int(read())):
	n = int(read())
	s = read()
	segs = list()
	last = s[0]
	count = 0
	for i in s:
		if i == last:
			count += 1
		else:
			last = i
			segs.append(count)
			count = 1
	segs.append(count)
	i = j = 0
	steps = 0
	n = len(segs)
	while j < n:
		if j < i:
			j = i
		while j < n and segs[j] < 2:
			j += 1
		if j < n:
			steps += 1
			segs[j] -= 1
		else:
			break
		i += 1
	steps += ceil((n - i) / 2)
	print(steps)


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *
from math import sqrt, pi
import math
from itertools import permutations
from copy import deepcopy

def main():
	for t in range(int(input())):
		n = int(input())
		s = input().strip()
		i = 0
		l = []
		while i < n:
			j = i
			while j < n - 1:
				if s[j] != s[j + 1]:
					break
				j += 1
			l.append(j - i + 1)
			i = j + 1
		m = len(l)
		i = 0
		j = 0
		ans = 0
		while i < m:
			if l[i] > 1:
				ans += 1
				i += 1
			else:
				j = max(j, i + 1)
				while j < m:
					if l[j] > 1:
						break
					j += 1
				if j == m:
					ans += (j - i) // 2 + (j - i) % 2
					i = m
					break
				while l[j] > 1 and l[i] == 1:
					i += 1
					l[j] -= 1
					ans += 1
					if i == m:
						break
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys, math
input = sys.stdin.readline
t = int(input())
for r in range(t):
	n = int(input())
	s = input().strip('\n')
	l = []
	for i in s:
		l.append(i)
	ans = 0
	i = 0
	j = 0
	while i < n - 1:
		if l[i] == '#':
			i += 1
			continue
		if l[i] == l[i + 1]:
			l[i] = '#'
			while j < n - 1:
				if l[j] == l[j + 1] or l[j] == '#':
					l[j] = '#'
					j += 1
				else:
					break
			l[j] = '#'
			j += 1
			ans += 1
		else:
			i += 1
	temp = 0
	for k in l:
		if k != '#':
			temp += 1
	ans += math.ceil(temp / 2)
	print(ans)


def main():
	n = int(input())
	line = input()
	turn_take = []
	prev = line[-1]
	can_be = 0
	for i in range(n - 2, -1, -1):
		if line[i] == prev:
			can_be += 1
		else:
			prev = line[i]
			turn_take.append(can_be)
	turn_take.append(can_be)
	turns = len(turn_take)
	taken = 0
	res = 0
	for i in range(1, turns + 1):
		if i > 1 and turn_take[-i] < turn_take[-i + 1]:
			taken = min(0, taken + turn_take[-i + 1] - turn_take[-i])
		if turn_take[-i] > -taken:
			taken -= 1
			res += 1
		else:
			res += (turns - i + 1) // 2
			if (turns - i + 1) % 2 != 0:
				res += 1
			break
	print(res)

def __starting_point():
	t = int(input())
	for i in range(t):
		main()
__starting_point()


import sys
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
input = sys.stdin.readline
getS = lambda : input().strip()
getN = lambda : int(input())
getList = lambda : list(map(int, input().split()))
getZList = lambda : [int(x) - 1 for x in input().split()]
INF = float('inf')
MOD = 10 ** 9 + 7
divide = lambda x: pow(x, MOD - 2, MOD)

def solve():
	n = getN()
	s = getS()
	ren = []
	prev = s[0]
	tmp = 0
	for c in s:
		if c != prev:
			ren.append(tmp)
			tmp = 0
		tmp += 1
		prev = c
	if tmp != 0:
		ren.append(tmp)
	lr = len(ren)
	yoyuu = n - lr
	used = 0
	ans = 0
	index = 0
	while True:
		ans += 1
		if yoyuu > 0:
			yoyuu -= 1
			used += 1
		else:
			index += 1
		if index == lr:
			break
		if ren[index] - 1 <= used:
			used -= ren[index] - 1
		else:
			yoyuu -= ren[index] - 1 - used
			used = 0
		index += 1
		if index == lr:
			break
	print(ans)

def main():
	n = getN()
	for _ in range(n):
		solve()
	return
main()


from itertools import groupby
t = int(input())
for _ in range(0, t):
	n = int(input())
	ss = [i for i in input()]
	sg = [len(list(g)) for (s, g) in groupby(ss)]
	(i, j, ans) = (0, 0, 0)
	while i < len(sg):
		j = max(j, i)
		if sg[i] > 1:
			i += 1
		else:
			while j < len(sg) and sg[j] == 1:
				j += 1
			if j < len(sg) and sg[j] > 1:
				sg[j] -= 1
				i += 1
			else:
				i += 2
		ans += 1
	print(ans)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=300006, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += 1
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += 1
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if not val:
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right and self.temp.right.count > 0:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
			self.temp.count -= 1
		return xor ^ self.temp.data
for ik in range(int(input())):
	n = int(input())
	s = input()
	seg = []
	c = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			c += 1
		elif c > 0:
			seg.append(c)
			c = 1
	if c > 0:
		seg.append(c)
	i = 0
	ans = 0
	j = 0
	tr = 0
	for i in range(len(seg)):
		if tr == 1:
			tr = 0
			continue
		if seg[i] == 1:
			j = max(i + 1, j)
			f = 0
			while j < len(seg):
				if seg[j] > 1:
					seg[j] -= 1
					f = 1
					break
				j += 1
			if f == 0:
				tr = 1
		ans += 1
	print(ans)


from collections import deque
from sys import *
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input() + ' '
	unique = deque()
	last = s[0]
	for i in range(1, n + 1):
		if s[i] != last[0]:
			unique.append(len(last))
			last = ''
		last += s[i]
	(i, j, ans) = (0, 0, 0)
	while i < len(unique):
		ans += 1
		j = max(j, i)
		flag = 0
		while j < len(unique):
			if unique[j] > 1:
				flag = 1
				unique[j] -= 1
				break
			j += 1
		if not flag:
			i += 1
		i += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s1 = [1]
	for j in range(1, n):
		if s[j] == s[j - 1]:
			s1[len(s1) - 1] += 1
		else:
			s1.append(1)
	c = 0
	p = 0
	for j in range(len(s1)):
		if s1[j] > 1:
			if j == 0:
				c += 1
			elif s1[j] > p:
				c += p
				if s1[j] > p + 1:
					p = 0
					c += 1
				else:
					p = 1
			else:
				c += s1[j] - 1
				p -= s1[j] - 1
				p += 1
		else:
			p += 1
	c += (p + 1) // 2
	print(c)


n = int(input())
for i in range(n):
	f = int(input())
	s = str(input())
	ans = 0
	bor = 0
	cnt = 1
	for j in range(1, f):
		if s[j - 1] == s[j]:
			bor += 1
			bor = min(bor, cnt)
		else:
			cnt += 1
	print(bor + (cnt - bor + 1) // 2)


import sys
from collections import defaultdict
input = sys.stdin.readline
from math import ceil
for _ in range(int(input())):
	n = int(input())
	s = list(input().strip())
	if len(set(s)) == 1:
		print(1)
		continue
	lis = [1]
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			lis[-1] += 1
		else:
			lis.append(1)
	ind = []
	for i in range(len(lis)):
		if lis[i] > 1:
			ind.append(i)
	c = 0
	i = 0
	j = 0
	m = len(ind)
	while i < len(lis):
		if lis[i] > 1:
			i += 1
			j += 1
		elif j >= m:
			c += ceil((len(lis) - i) / 2)
			break
		else:
			i += 1
			lis[ind[j]] -= 1
			if lis[ind[j]] == 1:
				j += 1
		c += 1
	print(c)


from functools import reduce
import os
import sys
from collections import *
from math import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def arr():
	return [int(i) for i in input().split()]

def sarr():
	return [int(i) for i in input()]

def starr():
	return [str(x) for x in input().split()]

def inn():
	return int(input())

def svalue():
	return tuple(map(str, input().split()))

def parr():
	return [value() for i in range(n)]
mo = 1000000007
inf = 1e+18
div = 998244353
for _ in range(inn()):
	n = inn()
	a = [int(x) for x in input()]
	ans = 0
	i = 0
	c = 0
	while i < n:
		if i < n - 1 and a[i] != a[i + 1]:
			a[i] = -1
			i += 1
			c += 1
		elif i < n - 1 and a[i] == a[i + 1]:
			if c > 0:
				a[i] = -1
				i += 1
				c -= 1
			else:
				val = a[i]
				while i < n and a[i] == val:
					a[i] = -1
					i += 1
			ans += 1
		else:
			c += 1
			i += 1
	ans += ceil(c / 2)
	print(ans)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

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

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write('\n'.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = 10 ** 9 + 7
for t in range(int(data())):
	n = int(data())
	s = data()
	ind = 0
	l = []
	for i in range(1, n):
		if s[i] != s[i - 1]:
			l.append(i - ind)
			ind = i
	l.append(n - ind)
	l = l[::-1]
	i = 0
	ans = 0
	j = len(l) - 1
	while l:
		if l[-1] > 1:
			ans += 1
			l.pop()
			j -= 1
		else:
			j = min(j, len(l) - 1)
			while j >= 0 and l[j] == 1:
				j -= 1
			if j == -1:
				l.pop()
				if l:
					l.pop()
			else:
				l.pop()
				l[j] -= 1
			ans += 1
	out(ans)


from collections import deque
import itertools as I
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	gps = enumerate(map(lambda x: len(list(x[1])), I.groupby(s)))
	gps_more_than_one = deque(filter(lambda x: x[1] > 1, gps))
	n_gps_ones = n - sum(map(lambda x: x[1], gps_more_than_one))
	ops = 0
	i = 0
	while gps_more_than_one or n_gps_ones:
		if gps_more_than_one:
			gps_more_than_one[0] = (gps_more_than_one[0][0], gps_more_than_one[0][1] - 1)
			if gps_more_than_one[0][0] == i:
				gps_more_than_one.popleft()
			elif gps_more_than_one[0][1] == 1:
				gps_more_than_one.popleft()
			else:
				n_gps_ones -= 1
			i += 1
		else:
			n_gps_ones = max(0, n_gps_ones - 2)
			i += 2
		ops += 1
	print(ops)


import heapq
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	lst = []
	i = 0
	while i < n:
		j = i
		while j < n and s[i] == s[j]:
			j += 1
		lst.append(j - i)
		i = j
	i = 0
	j = 0
	cnt = 0
	while i < len(lst):
		if lst[i] == 1:
			j = max(i + 1, j)
			while j < len(lst) and lst[j] <= 1:
				j += 1
			if j == len(lst):
				lst.pop()
				j -= 1
			else:
				lst[j] -= 1
		i += 1
		cnt += 1
	print(cnt)


import math
t = int(input())
for q in range(t):
	n = int(input())
	s = input()
	val = 0
	prev = -1
	for i in s:
		if i == prev:
			val += 1
		prev = i
	turn = 0
	dolg = 0
	prev = -1
	prevturn = False
	for i in s:
		if i != prev:
			if dolg == val:
				if prevturn:
					prevturn = False
				else:
					turn += 1
					prevturn = True
			else:
				prevturn = False
				turn += 1
				dolg += 1
		else:
			dolg = max(dolg - 1, 0)
			val -= 1
		prev = i
	print(turn)


from sys import stdin, stdout
import math, bisect
from collections import Counter, deque, defaultdict
L = lambda : list(map(int, stdin.readline().strip().split()))
M = lambda : map(int, stdin.readline().strip().split())
I = lambda : int(stdin.readline().strip())
S = lambda : stdin.readline().strip()
C = lambda : stdin.readline().strip().split()

def pr(a):
	return ' '.join(list(map(str, a)))

def solve():
	n = I()
	s = S()
	a = []
	b = []
	c = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			a += [s[i - 1]]
			b += [c]
			c = 1
		else:
			c += 1
	a += [s[-1]]
	b += [c]
	l = sum(b) - len(b)
	(ans, x) = (0, 0)
	while len(b):
		if l > x:
			x += 1
			x -= b[0] - 1
			if x < 0:
				x = 0
			l -= b[0] - 1
			b.pop(0)
		else:
			b.pop(0)
			if len(b):
				b.pop()
		ans += 1
	print(ans)
for _ in range(I()):
	solve()


from collections import deque, defaultdict
from heapq import heapify, heappop
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	kol = deque([1])
	for x in range(1, n):
		if s[x] != s[x - 1]:
			kol.append(1)
		else:
			kol[-1] += 1
	res = 0
	j = 0
	for (i, x) in enumerate(kol):
		while kol[i] > 1 and j <= i:
			kol[i] -= 1
			j += 1
			res += 1
	print(res + (len(kol) - j + 1) // 2)


import math
REMOVE_VALUE = 2
NO_BLOCK = -1

def find_first_two_block(start_index, s):
	i = start_index
	while i + 1 < len(s) and (s[i] == REMOVE_VALUE or s[i] != s[i + 1]):
		i += 1
	if i + 1 == len(s):
		return NO_BLOCK
	return i

def test_case(s):
	op = 0
	index = 0
	block_ix = 0
	nbr_deleted = 0
	while nbr_deleted != len(s):
		block_ix = find_first_two_block(block_ix, s)
		if block_ix == NO_BLOCK:
			left = 0
			while index < len(s):
				if s[index] != REMOVE_VALUE:
					left += 1
				index += 1
			op += math.ceil(left / 2)
			break
		op += 1
		s[block_ix] = REMOVE_VALUE
		nbr_deleted += 1
		while index < len(s) and s[index] == REMOVE_VALUE:
			index += 1
		if index == len(s):
			break
		head_value = s[index]
		remove_first = True
		while remove_first:
			if s[index] != REMOVE_VALUE:
				s[index] = REMOVE_VALUE
				nbr_deleted += 1
			index += 1
			if index >= len(s) or (s[index] != REMOVE_VALUE and head_value != s[index]):
				remove_first = False
	print(op)
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, list(input())))
	test_case(s)


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	n = stdin.readline()
	stri = stdin.readline()
	lst = []
	count = 0
	char = stri[0]
	for i in range(len(stri) - 1):
		if char == stri[i]:
			count += 1
		else:
			lst.append(count)
			char = stri[i]
			count = 1
	lst.append(count)
	current = 0
	ans = 0
	to_delete = 0
	while to_delete < len(lst):
		current = max(to_delete, current)
		while lst[current] <= 1:
			current += 1
			if current == len(lst):
				lst.pop(-1)
				current -= 2
				ans += 1
				break
		else:
			lst[current] -= 1
			ans += 1
		if len(lst) > to_delete and lst[to_delete] > 0:
			lst[to_delete] = 0
		else:
			break
		to_delete += 1
	print(ans)


def ans(s, n):
	temp = 1
	curr = s[0]
	seq = []
	i = 1
	while i < n:
		if s[i] == curr:
			temp += 1
		else:
			seq.append(temp)
			temp = 1
			curr = s[i]
		i += 1
	seq.append(temp)
	answer = 0
	if len(seq) == 1:
		return 1
	j = 0
	while j < len(seq) and seq[j] == 1:
		j += 1
	if j == len(seq):
		if len(seq) % 2:
			return len(seq) // 2 + 1
		else:
			return len(seq) // 2
	i = 0
	while i < len(seq) and j < len(seq):
		if i == j:
			answer += 1
			i += 1
			j += 1
			while j < len(seq) and seq[j] == 1:
				j += 1
			if j == len(seq):
				break
		else:
			answer += 1
			i += 1
			seq[j] -= 1
			while j < len(seq) and seq[j] == 1:
				j += 1
			if j == len(seq):
				break
	x = len(seq) - i
	if x % 2:
		answer += x // 2 + 1
	else:
		answer += x // 2
	return answer
m = int(input())
for j in range(m):
	n = int(input())
	s = input()
	print(ans(s, n))


import sys, os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
R = lambda : map(int, input().split())
for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = 0
	now = s[0]
	a = []
	for i in s:
		if i == now:
			cnt += 1
		else:
			now = i
			a.append(cnt)
			cnt = 1
	a.append(cnt)
	cur = 0
	ans = 0
	(it, n) = (0, len(a))
	while it < n:
		if a[it] == 0:
			it += 1
			continue
		cur = max(cur, it + 1)
		if a[it] > 1:
			ans += 1
		else:
			while cur < n and a[cur] <= 1:
				cur += 1
			if cur < n:
				a[cur] -= 1
				ans += 1
			else:
				ans += (sum(a[it:]) + 1) // 2
				break
		it += 1
	print(ans)


import sys

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def string(s):
	return ''.join(s)

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def bo(i):
	return ord(i) - ord('A')

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

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

def gh():
	sys.stdout.flush()

def isvalid(i, j):
	return 0 <= i < n and 0 <= j < m and (a[i][j] != '.')

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
while t > 0:
	t -= 1
	n = fi()
	s = si()
	c = 0
	a = []
	no = -1
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			if c > 0 and no == -1:
				no = len(a)
			a.append(c + 1)
			c = 0
		else:
			c += 1
	a.append(c + 1)
	if no == -1 and c > 0:
		no = len(a) - 1
	op = i = 0
	while i < len(a):
		if a[i] == 1:
			if no < i:
				no = i
				while no < len(a) and a[no] == 1:
					no += 1
			if no != len(a) and no >= i:
				a[no] -= 1
				if a[no] == 1:
					while no < len(a) and a[no] == 1:
						no += 1
				i += 1
				op += 1
			else:
				i += 2
				op += 1
		else:
			i += 1
			op += 1
	print(op)


for nt in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	c = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			ans += 1
			ans = min(ans, c)
		else:
			c += 1
	print(ans + (c - ans + 1) // 2)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
from math import ceil, floor, sqrt, pow
for _ in range(N()):
	n = N()
	s = input()
	data = []
	now = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			data.append(now)
			now = 1
		else:
			now += 1
	data.append(now)
	data = data[::-1]
	res = 0
	p = len(data) - 1
	while data:
		res += 1
		p = min(p, len(data) - 1)
		while p >= 0 and data[p] == 1:
			p -= 1
		if p >= 0:
			data[p] -= 1
		else:
			data.pop()
		if data:
			data.pop()
	print(res)


def string_deletion():
	test_cases = int(input())
	for t in range(test_cases):
		n = int(input())
		string = input()
		dup_count = 0
		dup = [0]
		op_count = 1
		op = [1]
		for x in range(1, len(string)):
			remaining = len(string) - len(op)
			dup_available = op[x - 1] - dup[x - 1]
			if remaining <= dup_available:
				break
			if string[x] != string[x - 1]:
				op_count += 1
			else:
				dup_count += 1
			dup_count = min(dup_count, op_count)
			op += [op_count]
			dup += [dup_count]
		print(op[len(op) - 1])
string_deletion()


import math
for _ in range(int(input())):
	n = int(input())
	a = str(input())
	d = [1]
	prev = a[0]
	for i in range(1, n):
		if a[i] == prev:
			d[-1] += 1
		else:
			prev = a[i]
			d.append(1)
	ans = 0
	i = j = 0
	n = len(d)
	c = 0
	flag = True
	while i < n and (j < n and d[n - 1] != 0):
		if flag == True:
			for k in range(j, n):
				if d[k] > 1:
					j = k
					break
				else:
					j = k
			d[j] -= 1
		for k in range(i, n):
			if d[k] > 0:
				i = k
				break
		d[i] = 0
		ans += 1
	count = 0
	for i in d:
		if i > 0:
			count += 1
	ans += (count + 1) // 2
	print(ans)


import math
for _ in range(int(input())):
	int(input())
	arr = list(map(int, list(input())))
	n = len(arr)
	new = []
	l = arr[0]
	t = 0
	for i in range(n):
		if arr[i] == l:
			t += 1
		else:
			new.append(t)
			l = arr[i]
			t = 1
	new.append(t)
	arr = new
	n = len(arr)
	ones = 0
	ans = 0
	for i in range(n):
		if arr[i] == 1:
			ones += 1
		else:
			m = 0
			if i != n - 1:
				m = 1
			canGet = min(ones, arr[i] - m)
			ones -= canGet
			ans += canGet
			t = arr[i] - canGet
			if t > 1:
				ans += 1
			elif t == 1:
				ones += 1
	print(ans + math.ceil(ones / 2))


from sys import stdin, stdout
from math import gcd
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	c = int(s[0])
	cnt = 0
	a = []
	for i in range(n):
		if s[i] == str(c):
			cnt += 1
		else:
			a.append(cnt)
			cnt = 1
			c ^= 1
	a.append(cnt)
	(i, j) = (0, 0)
	ans = 0
	n = len(a)
	while i < n:
		if i > j or a[j] < 2:
			j += 1
			if j < n:
				while a[j] < 2:
					j += 1
					if j >= n:
						break
		if j >= n:
			ans += j - i + 1 >> 1
			break
		a[j] -= 1
		i += 1
		ans += 1
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	(ones, out) = (0, 0)
	x = s[0]
	i = 1
	l = 1
	while i < n:
		if s[i] == x:
			l += 1
			i += 1
		else:
			if l == 1:
				ones += 1
			elif l > 2:
				extra = l - 2
				out += 1
				if extra >= ones:
					out += ones
					ones = 0
				else:
					ones -= extra
					out += extra
			else:
				out += 1
			x = s[i]
			i += 1
			l = 1
	if l == 1:
		ones += 1
	elif l == 2:
		out += 1
	else:
		out += 1
		extra = l - 2
		if extra >= ones:
			out += ones
			ones = 0
		else:
			ones -= extra
			out += extra
	out += math.ceil(ones / 2)
	print(out)


from math import sqrt, ceil, gcd
from collections import defaultdict
import heapq

def modInverse(b, m):
	g = gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)
from itertools import permutations

def solve():
	n = int(input())
	s = list(input())
	i = 0
	ans = []
	no = []
	ind = 0
	while i < n:
		z = s[i]
		cnt = 0
		while i < n and s[i] == z:
			cnt += 1
			i += 1
		ans.append(cnt)
		if cnt > 1:
			no.append([cnt, ind])
		ind += 1
	i = 0
	fin = 0
	seti = set()
	n = len(ans)
	while i < n:
		if ans[i] > 1:
			fin += 1
			seti.add(i)
		else:
			while no != [] and (no[0][1] in seti or no[0][0] == 1):
				no.pop(0)
			if no != []:
				(a, b) = no[0]
				ans[b] -= 1
				no[0][0] -= 1
				fin += 1
			else:
				fin += 1
				n -= 1
		i += 1
	print(fin)
t = int(input())
for _ in range(t):
	solve()


import math

def mi():
	return map(int, input().strip().split(' '))
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	cnt = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			ans += 1
			ans = min(ans, cnt)
		else:
			cnt += 1
	ans += (cnt - ans + 1) // 2
	print(ans)


def ceil(a, b):
	return (a + b - 1) // b
for _ in range(int(input())):
	n = int(input())
	s = input()
	streak = 1
	prev = s[0]
	res = []
	for i in range(1, n):
		if s[i] == prev:
			streak += 1
		else:
			prev = s[i]
			res.append(streak)
			streak = 1
	res.append(streak)
	ans = 0
	next_max = 0
	t = len(res)
	for i in range(t):
		next_max = max(next_max, i)
		while next_max < t and res[next_max] == 1:
			next_max += 1
		if next_max != t:
			res[next_max] -= 1
			ans += 1
		ans += 1
	print(ceil(ans, 2))


import os
import sys
from io import BytesIO, IOBase
_str = str
BUFSIZE = 8192

def str(x=b''):
	return x if type(x) is bytes else _str(x).encode()

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

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

def mpint():
	return map(int, sys.stdin.readline().split(' '))

def itg():
	return int(sys.stdin.readline())

def solve():
	n = itg()
	s = inp()
	cnt = 0
	char = s[0]
	arr = []
	for c in s:
		if c == char:
			cnt += 1
		else:
			arr.append(cnt)
			cnt = 1
			char = c
	arr.append(cnt)
	ans = delete_idx = i = 0
	while i < len(arr):
		ans += 1
		while delete_idx < len(arr) and arr[delete_idx] <= 1:
			delete_idx += 1
		if delete_idx < len(arr) and arr[delete_idx] > 1:
			arr[delete_idx] -= 1
		else:
			i += 1
		i += 1
		delete_idx = max(i, delete_idx)
	return ans
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
for _ in range(itg()):
	print(solve())


import sys
input = sys.stdin.readline
from itertools import groupby

def HalfDead():
	n = int(input())
	s = input().strip()
	a = [len(list(g)) for (_, g) in groupby(s)]
	cnt = 0
	for (i, v) in enumerate(a):
		if v == 1:
			cnt += 1
		else:
			r = v - 2
			cnt = max(0, cnt - r)
	print(len(a) - cnt // 2)
for _ in range(int(input())):
	HalfDead()


from itertools import groupby
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	(l, r) = (0, n - 1)
	result = 0
	runEncoding = [len(list(group)) for (_, group) in groupby(s)]
	multiIndices = [i for i in range(len(runEncoding)) if runEncoding[i] > 1]
	index = 0
	mIndex = 0
	mExists = True if len(multiIndices) > 0 else False
	end = len(runEncoding) - 1
	while index <= end:
		if mExists and index == multiIndices[mIndex]:
			mIndex += 1
			if mIndex >= len(multiIndices):
				mExists = False
		if runEncoding[index] == 1:
			if not mExists:
				end -= 1
			else:
				runEncoding[multiIndices[mIndex]] -= 1
				if runEncoding[multiIndices[mIndex]] == 1:
					mIndex += 1
				if mIndex >= len(multiIndices):
					mExists = False
		result += 1
		index += 1
	print(result)


import sys
import math
from collections import Counter, defaultdict
LI = lambda : list(map(int, input().split()))
MAP = lambda : map(int, input().split())
IN = lambda : int(input())
S = lambda : input()

def case():
	n = IN()
	s = S()
	b = []
	c = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			b += [c]
			c = 1
		else:
			c += 1
	b += [c]
	l = sum(b) - len(b)
	(ans, ye) = (0, 0)
	while len(b) > 0:
		if l > ye:
			ye += 1
			ye -= b[0] - 1
			if ye < 0:
				ye = 0
			l -= b[0] - 1
			b.pop(0)
		else:
			b.pop(0)
			if len(b) > 0:
				b.pop()
		ans += 1
	print(ans)
for _ in range(IN()):
	case()


import sys
import math
original_stdout = sys.stdout
var_for_sublime = False
if var_for_sublime:
	fin = open('input.txt', 'r')
	fout = open('output.txt', 'w')
	sys.stdout = fout

	def give_string():
		return fin.readline()
else:
	fin = sys.stdin
	fout = sys.stdout

	def give_string():
		return fin.buffer.readline()

def give_list():
	return list(map(int, give_string().split()))

def give_int():
	return int(give_string())
MOD = 1000000000.0 + 7

def modpow(a, p):
	ans = 1
	while p:
		if p & 1:
			ans *= a
			ans %= MOD
		p >>= 1
		a *= a
		a %= MOD
	return ans

def fac_cal(n):
	ans = 1
	for i in range(1, n + 1):
		ans *= i
		ans %= MOD
	return ans

def solve():
	t = 1
	n = give_int()
	s = give_string()
	i = 0
	ans = 0
	c10 = 0
	while i < n:
		temp = s[i]
		co = 0
		while i < n and temp == s[i]:
			co += 1
			i += 1
		if co == 1:
			c10 += 1
		elif c10 >= co:
			ans += co - 1
			c10 -= co - 1
			c10 += 1
		else:
			co -= c10
			ans += c10
			if co == 1:
				c10 = 1
			else:
				ans += 1
				c10 = 0
	ans += math.ceil(c10 / 2.0)
	print(int(ans))

def Hey_Yashwant():
	try:
		t = 1
		t = give_int()
		for i in range(t):
			solve()
	finally:
		fin.close()
		fout.close()
		sys.stdout = original_stdout
Hey_Yashwant()


def find_cnt_seg(string, start):
	l = len(string)
	ind = start
	while ind < l - 1:
		if string[ind] == string[ind + 1]:
			return ind
		ind += 1
	if ind >= l - 1:
		return -1
t = int(input())
for ii in range(t):
	n = int(input())
	s = input()
	m = [False] * len(s)
	cnt = 0
	i = 0
	ind = find_cnt_seg(s, 0)
	if ind == i:
		i += 1
	if ind == -1:
		print(n // 2 + n % 2)
		continue
	while i < n:
		cnt += 1
		m[ind] = True
		start = s[i]
		while i < n:
			if s[i] == start:
				m[i] = True
				i += 1
			elif m[i] == True:
				i += 1
			else:
				break
		j = max(i, ind)
		while j < n:
			if m[j] == True:
				j += 1
			else:
				break
		ind = find_cnt_seg(s, j)
		if ind == -1:
			break
	int_ = 0
	for i in m:
		if i == False:
			int_ += 1
	print(cnt + int_ // 2 + int_ % 2)


from __future__ import division, print_function
import bisect
import math
import heapq
import itertools
import sys
from collections import deque
from atexit import register
from collections import Counter
from functools import reduce
if sys.version_info[0] < 3:
	from io import BytesIO as stream
else:
	from io import StringIO as stream
if sys.version_info[0] < 3:

	class dict(dict):

		def items(self):
			return dict.iteritems(self)

		def keys(self):
			return dict.iterkeys(self)

		def values(self):
			return dict.itervalues(self)
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip

def sync_with_stdio(sync=True):
	global input, flush
	if sync:
		flush = sys.stdout.flush
	else:
		sys.stdin = stream(sys.stdin.read())
		input = lambda : sys.stdin.readline().rstrip('\r\n')
		sys.stdout = stream()
		register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		cnt = 1
		prev = s[0]
		v = []
		for i in range(1, n):
			if s[i] == prev:
				cnt += 1
			else:
				v.append(cnt)
				cnt = 1
				prev = s[i]
		v.append(cnt)
		n = len(v)
		arr = [0] * (n + 5)
		last = -1
		for i in range(n - 1, -1, -1):
			arr[i] = last
			if v[i] != 1:
				last = i
		a = last
		cnt = 0
		i = 0
		while a != -1:
			v[a] -= 1
			if v[a] == 1 or i == a:
				a = arr[a]
			cnt += 1
			i += 1
		cnt += int(math.ceil((n - i) / 2))
		print(cnt)
sync_with_stdio(False)
main()


t = int(input())
for j in range(t):
	n = int(input())
	s = input()
	(i, op, future) = (0, 0, 0)
	left = n
	while left > 0:
		op += 1
		if i == n - 1:
			break
		symbol = s[i]
		flag = True
		left -= 1
		i += 1
		while left != 0 and symbol == s[i]:
			if future > 0:
				future -= 1
				left += 1
			else:
				flag = False
			left -= 1
			i += 1
		if flag:
			future += 1
			left -= 1
	print(op)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	paq = []
	l = 1
	last_seen = s[0]
	for i in range(1, len(s)):
		if s[i] == last_seen:
			l += 1
		else:
			paq.append(l)
			l = 1
			last_seen = s[i]
	paq.append(l)
	vie = 0
	num = 0
	reste = len(paq)
	next_greater = 0
	while reste > 0:
		if next_greater < len(paq) and (next_greater < vie or paq[next_greater] <= 1):
			j = max(next_greater, vie)
			while j < len(paq) and paq[j] <= 1:
				j += 1
			next_greater = j
		i = next_greater
		if i == len(paq):
			vie += 2
			reste -= 2
		else:
			paq[i] -= 1
			reste -= 1
			vie += 1
		num += 1
	print(num)


import sys
from collections import defaultdict as dd
from collections import Counter as cc
from queue import Queue
import math
import itertools
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
for _ in range(int(input())):
	q = int(input())
	w = input()
	e = []
	r = w[0]
	t = 0
	for i in range(q):
		if r == w[i]:
			t += 1
		else:
			r = w[i]
			e.append(t)
			t = 1
	if t != 0:
		e.append(t)
	s = 0
	j = 0
	d = len(e)
	f = q
	for i in range(d):
		if e[i] > 1:
			s += 1
			d -= 1
			f -= e[i]
			s += min(e[i] - 2, j)
			j -= min(e[i] - 2, j)
		elif f - d > 0:
			f -= 1
			d -= 1
			j += 1
		else:
			d = d + j
			j = 0
			if d % 2 == 0:
				s += d // 2
			else:
				s += d // 2 + 1
			break
	if j != 0:
		if j % 2 == 0:
			s += j // 2
		else:
			s += j // 2 + 1
	print(s)


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from itertools import groupby
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	L = []
	for (_, gr) in groupby(S):
		n = len(list(gr))
		L.append(n)
	idx_op1 = 0
	idx_op2 = 0
	while len(L) - idx_op2 > 0:
		while idx_op1 < len(L) and (idx_op1 < idx_op2 or L[idx_op1] <= 1):
			idx_op1 += 1
		if idx_op1 >= len(L):
			L.pop()
		else:
			L[idx_op1] -= 1
		idx_op2 += 1
	print(idx_op2)


z = input
o = []
for _ in range(int(z())):
	n = int(z())
	a = []
	p = ''
	for i in z().strip():
		if i == p:
			a[-1] += 1
		else:
			a += [1]
			p = i
	a = a[::-1]
	r = 0
	i = len(a) - 1
	while a:
		while i and a[i] < 2:
			i -= 1
		if i < 1 and a[i] < 2:
			break
		a[i] -= 1
		a.pop()
		r += 1
		if i >= len(a):
			i -= 1
	r += (len(a) + 1) // 2
	o += [str(r)]
print('\n'.join(o))


import math
from collections import Counter, defaultdict, deque

def f(n, s):
	cur = '?'
	val = 0
	segs = []
	for c in s:
		if cur != c:
			if val:
				segs.append(val)
			val = 1
			cur = c
		else:
			val += 1
	if val:
		segs.append(val)
	tot = 0
	debt = 0
	for x in segs:
		tot += x - 1
	ans = 0
	kill_next = 0
	cnt_next = 0
	for i in range(len(segs)):
		if kill_next:
			if cnt_next:
				ans += 1
			cnt_next ^= 1
			continue
		ans += 1
		segs[i] -= 1
		if debt < tot:
			debt += 1
		else:
			kill_next = 1
		debt -= min(debt, segs[i])
		tot -= segs[i]
	return ans
t = int(input())
result = []
for i in range(t):
	n = int(input())
	s = input().strip()
	result.append(f(n, s))
for i in range(t):
	print(result[i])


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	s = input().rstrip()
	changes = 1
	spare = 0
	before = s[0]
	spare_can = 1
	for j in range(n - 1):
		if s[j + 1] == before:
			if spare_can > 0:
				spare_can -= 1
				spare += 1
		else:
			before = s[j + 1]
			changes += 1
			spare_can += 1
	ans = 0
	ans += spare
	changes -= spare
	ans += (changes + 1) // 2
	print(ans)


from itertools import groupby
for _ in [0] * int(input()):
	n = int(input())
	s = input()
	c = [len(list(x[1])) for x in groupby(s)]
	m = len(c)
	dup_idx = []
	for (i, j) in enumerate(c):
		if j > 1:
			dup_idx.append(i)
	dup_idx.reverse()
	curr = 0
	while dup_idx:
		i = dup_idx[-1]
		if i < curr:
			dup_idx.pop()
			continue
		c[i] -= 1
		if c[i] == 1:
			dup_idx.pop()
		curr += 1
	ans = curr + (m - curr + 1) // 2
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if n == 1:
		print(1)
		continue
	ans = 0
	partition = list()
	start = 0
	for end in range(1, n):
		if s[end] != s[start]:
			size = end - start
			partition.append(size)
			start = end
	size = n - start
	partition.append(size)
	left = right = 0
	length = len(partition)
	ans = 0
	while left < length:
		while right < length and partition[right] == 1:
			right += 1
		if right != length and partition[right] > 1:
			partition[right] -= 1
			left += 1
			if left == right + 1:
				right += 1
		elif right == length:
			left += 2
		ans += 1
	print(ans)


from math import ceil

def stringdel(string):
	q = []
	curr = 0
	for i in range(len(string)):
		if i > 0 and string[i] != string[i - 1]:
			curr += 1
		if i > 0 and string[i] == string[i - 1]:
			q.append(curr)
	deleted = 0
	score = 0
	for i in range(len(string)):
		if len(q) == 0:
			break
		q.pop(0)
		deleted += 1
		score += 1
		while q and q[0] == i:
			q.pop(0)
			deleted += 1
		deleted += 1
	score += ceil((len(string) - deleted) / 2)
	return score
for i in range(int(input())):
	a = input()
	print(stringdel(input()))


from sys import *
from math import *
from bisect import *
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	a = list(map(int, input()))
	b = []
	x = 1
	ans = 0
	for i in range(1, n):
		if a[i] == a[i - 1]:
			x += 1
		else:
			b.append(x)
			x = 1
	b.append(x)
	i = j = 0
	while i < len(b):
		if b[i] <= 1:
			j = max(i + 1, j)
			while j < len(b) and b[j] <= 1:
				j += 1
			if j == len(b):
				b.pop(-1)
				j -= 1
			else:
				b[j] -= 1
		ans += 1
		i += 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
import bisect
from collections import Counter
import bisect
from collections import deque
for _ in range(int(input())):
	n = int(input())
	op = 0
	s = input()
	if n == 1:
		print(1)
	else:
		ls = []
		op = 0
		var = 1
		ind = []
		for i in range(1, n):
			if s[i] == s[i - 1]:
				var += 1
				if i == n - 1:
					ls.append(var)
					if var > 1:
						ind.append(len(ls) - 1)
			else:
				ls.append(var)
				if var > 1:
					ind.append(len(ls) - 1)
				var = 1
				if i == n - 1:
					ls.append(var)
		i = 0
		j = 0
		while i < len(ls):
			if ls[i] == 0:
				i += 1
				continue
			if ls[i] >= 2:
				op += 1
				i += 1
			else:
				j = max(i + 1, j)
				while j + 1 < len(ls) and ls[j] <= 1:
					j += 1
				if j < len(ls) and ls[j] > 1:
					ls[j] -= 1
					i += 1
					op += 1
				elif i + 1 >= n:
					op += 1
					break
				else:
					i += 2
					op += 1
		print(op)


for _ in range(int(input())):
	n = int(input())
	s = input()
	start = 1
	end = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			end += 1
			end = min(end, start)
		else:
			start += 1
	print(end + (start - end + 1) // 2)


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	n = int(input())
	S = input().strip()
	L = [1]
	for i in range(1, n):
		if S[i] == S[i - 1]:
			L[-1] += 1
		else:
			L.append(1)
	de = 0
	i = 0
	ANS = 0
	LEN = len(L)
	flag = 0
	while de < LEN:
		if flag == 0:
			i = max(i, de)
			while i < LEN:
				if L[i] > 1:
					break
				else:
					i += 1
			if i == LEN:
				flag = 1
			else:
				L[i] -= 1
		if flag == 0:
			de += 1
			ANS += 1
		else:
			de += 2
			ANS += 1
	print(ANS)


for _ in range(int(input())):
	n = int(input())
	ar = list(input())
	li = []
	count = 1
	pre = ar[0]
	for i in range(1, n):
		if ar[i] == pre:
			count += 1
		else:
			li.append(count)
			count = 1
			pre = ar[i]
	if count != 0:
		li.append(count)
	ans = 0
	one = 0
	for i in range(len(li)):
		if li[i] == 1:
			one += 1
		elif li[i] > 2:
			ext = li[i] - 2
			if ext >= one:
				ans += one + 1
				one = 0
			else:
				ans += ext + 1
				one -= ext
		else:
			ans += 1
	if one % 2 == 0:
		ans += one // 2
	else:
		ans += one // 2 + 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		a = []
		cnt = 0
		prv = s[0]
		for c in s:
			if c == prv:
				cnt += 1
			else:
				a.append(cnt)
				prv = c
				cnt = 1
		a.append(cnt)
		(l, r, ans) = (0, 0, 0)
		n = len(a)
		while l < n:
			if a[l] == 1:
				if r < l:
					r = l + 1
				while r < n and a[r] == 1:
					r += 1
				if r < n:
					a[r] -= 1
				else:
					l += 1
			ans += 1
			l += 1
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def getint():
	return int(input())

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

def getint1():
	return list(map(lambda x: int(x) - 1, input().split()))
main()


import math as mt
import bisect
t = int(input())
import collections
import heapq
p = 10 ** 9 + 7

def ncr_util():
	inv[0] = inv[1] = 1
	fact[0] = fact[1] = 1
	for i in range(2, 300001):
		inv[i] = inv[i % p] * (p - p // i) % p
	for i in range(1, 300001):
		inv[i] = inv[i - 1] * inv[i] % p
		fact[i] = fact[i - 1] * i % p

def solve():
	l = []
	ch = 1
	(cnt, cnt1) = (1, 0)
	jst = 1
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			cnt += 1
		else:
			l.append(cnt)
			cnt = 1
	if cnt > 0:
		l.append(cnt)
	(suma, sub) = (0, 0)
	for i in range(len(l)):
		suma += l[i] - 1
	ans = 0
	for i in range(len(l)):
		x = min(sub, l[i] - 1)
		l[i] -= x
		sub -= x
		if l[i] > 1 and suma > 0:
			ans += 1
		elif suma <= 0:
			ans += (len(l) - i) // 2
			if (len(l) - i) % 2 != 0:
				ans += 1
			break
		else:
			sub += 1
			suma -= 1
			ans += 1
		suma -= l[i] - 1
	return ans
for _ in range(t):
	n = int(input())
	s = input()
	print(solve())


import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a = [1]
	for i in range(1, n):
		if s[i] == s[i - 1]:
			a[-1] += 1
		else:
			a.append(1)
	la = len(a)
	ans = 0
	for i in range(la):
		ans = min(ans + a[i] - 1, i + 1)
	ans = ans + (la - ans + 1) // 2
	print(ans)


t = int(input())
while t != 0:
	n = int(input())
	s = input()
	arr = []
	i = 0
	while i < n:
		p = s[i]
		c = 0
		while i < n and s[i] == p:
			c += 1
			i += 1
		arr.append(c)
	ans = 0
	temp = 0
	for i in range(len(arr)):
		if arr[i] != 1:
			p = arr[i] - 2
			if temp > 0 and p > 0:
				temp = max(0, temp - p)
			ans += 1
		else:
			temp += 1
			ans += 1
	print(ans - temp // 2)
	t -= 1


def main():
	n = int(input())
	s = input()
	(l, o) = (0, 0)
	(cnt, groups) = (0, [])
	while l < n:
		c = s[l]
		r = l
		while r + 1 < n and s[r + 1] == c:
			r += 1
		pre_len = r - l + 1
		groups.append(pre_len)
		l = r + 1
	(p, n) = (0, len(groups))
	i = 0
	while i < n:
		if groups[i] > 1:
			o += 1
			p += 1
			i += 1
		else:
			while p < n and groups[p] == 1:
				p += 1
			if p == n:
				i += 2
				o += 1
			else:
				groups[p] -= 1
				o += 1
				i += 1
	print(o)
for _ in range(int(input())):
	main()


def solution():
	n = int(input())
	s = input()
	l = []
	i = 0
	while i < n:
		j = i
		while i < n and s[i] == s[j]:
			i += 1
		l.append(i - j)
	d = 0
	pos = []
	for i in range(len(l)):
		d += l[i] - 1
		if l[i] - 1 > 0:
			pos.append(i)
	pos.reverse()
	ans = 0
	i = 0
	x = len(l)
	while i < x:
		if pos:
			ans += 1
			if l[i] - 1 > 0:
				pos.pop()
			else:
				y = pos.pop()
				l[y] -= 1
				if l[y] - 1 > 0:
					pos.append(y)
		else:
			ans += (x - i) // 2 + (x - i) % 2
			break
		i += 1
	print(ans)
t = int(input())
for _ in range(t):
	solution()


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	s = input() + 'X'
	que = []
	c = 1
	for i in range(n):
		if s[i] == s[i + 1]:
			c += 1
		else:
			que.append(c)
			c = 1
	more_than_2 = 0
	ans = 0
	deleted = 0
	for i in range(len(que)):
		if que[i] == 0:
			continue
		while more_than_2 + 1 <= len(que) and que[more_than_2] <= 1:
			more_than_2 += 1
		if more_than_2 == len(que):
			ans += (len(que) - deleted + 1) // 2
			break
		else:
			que[more_than_2] -= 1
			if i == more_than_2:
				more_than_2 += 1
			deleted += 1
			ans += 1
	print(ans)


import io
import os
import sys
import math
import heapq
input = sys.stdin.readline
mod = 10 ** 9 + 7
t = int(input())
for i in range(t):
	n = int(input())
	s = list(input().rstrip())
	arr = []
	st = s[0]
	c = 0
	for i in range(len(s)):
		if s[i] != st:
			arr.append(c)
			st = s[i]
			c = 0
		c += 1
	if c > 0:
		arr.append(c)
	limit = 0
	steps = 0
	for i in range(len(arr)):
		limit += 1
		if arr[i] > 1:
			red = arr[i] - 1
			gh = min(red, limit)
			arr[i] -= gh
			limit -= gh
			steps += gh
	ans = math.ceil((len(arr) + steps) / 2)
	print(ans)


import sys
import math
import collections
import itertools
input = sys.stdin.readline

def solve(N, S):
	S = S[:-1]
	A = [len(list(grp)) for (_, grp) in itertools.groupby(S)]
	N = len(A)
	ans = i = j = 0
	while i < N:
		j = max(i, j)
		while j < N and A[j] < 2:
			j += 1
		if j < N:
			A[j] -= 1
		else:
			N -= 1
		ans += 1
		i += 1
	return ans
for i in range(int(input())):
	print(solve(int(input()), input()))


def parseString(string):
	cur = string[0]
	subLen = 0
	ans = []
	for ele in string:
		if ele == cur:
			subLen += 1
		else:
			ans.append(subLen)
			subLen = 1
			cur = ele
	ans.append(subLen)
	return ans

def reduceNext(curIndex, lst):
	for i in range(curIndex, len(lst)):
		if lst[i] > 1:
			lst[i] -= 1
			return i
	lst.pop(len(lst) - 1)
	return len(lst) - 1

def main(string):
	subList = parseString(string)
	reducer = 0
	deleter = 0
	counter = 0
	while subList[-1] != 0:
		reducer = reduceNext(reducer, subList)
		counter += 1
		try:
			subList[deleter] = 0
		except IndexError:
			break
		deleter += 1
	return counter
tc = int(input())
for _ in range(tc):
	length = int(input())
	string = str(input())
	print(main(string))


from sys import stdin, stdout
input = stdin.readline
mp = lambda : map(int, input().split())
it = lambda : int(input())
from itertools import groupby
test = it()
for i in range(test):
	a = it()
	b = input().strip()
	l = []
	ind = []
	for (k, g) in groupby(b):
		l.append(len(list(g)))
		if l[-1] > 1:
			ind.append(len(l) - 1)
	st = 0
	ans = 0
	st_ind = 0
	if ind == []:
		print((a + 1) // 2)
		continue
	while st < len(l):
		if l[st] == 1:
			index = None
			for j in range(st_ind, len(ind)):
				if ind[j] >= st and l[ind[j]] > 1:
					index = ind[j]
					st_ind = j
					break
			if index == None:
				st += 1
			else:
				l[index] -= 1
		ans += 1
		st += 1
	print(ans)


t = int(input())
for you in range(t):
	n = int(input())
	s = input()
	l = []
	curr = '2'
	for i in range(n):
		if s[i] != curr:
			l.append(1)
			curr = s[i]
		else:
			l[-1] += 1
	z = len(l)
	ans = 0
	curr = 0
	for i in range(z):
		curr = min(curr + l[i] - 1, i + 1)
	ans = curr + (z - curr + 1) // 2
	print(ans)


from bisect import *
from collections import *
from math import *
from heapq import *
from typing import List
from itertools import *
from operator import *
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

@lru_cache(None)
def fact(x):
	if x < 2:
		return 1
	return fact(x - 1) * x

@lru_cache(None)
def per(i, j):
	return fact(i) // fact(i - j)

@lru_cache(None)
def com(i, j):
	return per(i, j) // fact(j)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 1
	res = 0
	for w in arr:
		res += w
		if res > x:
			res = w
		c += 1
	return c

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class smt:

	def __init__(self, l, r, arr):
		self.l = l
		self.r = r
		self.value = (1 << 31) - 1 if l < r else arr[l]
		mid = (l + r) // 2
		if l < r:
			self.left = smt(l, mid, arr)
			self.right = smt(mid + 1, r, arr)
			self.value &= self.left.value & self.right.value

	def setvalue(self, x, val):
		if self.l == self.r:
			self.value = val
			return
		mid = (self.l + self.r) // 2
		if x <= mid:
			self.left.setvalue(x, val)
		else:
			self.right.setvalue(x, val)
		self.value = self.left.value & self.right.value

	def ask(self, l, r):
		if l <= self.l and r >= self.r:
			return self.value
		val = (1 << 31) - 1
		mid = (self.l + self.r) // 2
		if l <= mid:
			val &= self.left.ask(l, r)
		if r > mid:
			val &= self.right.ask(l, r)
		return val

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d
t = N()
for i in range(t):
	n = N()
	s = input()
	arr = []
	for (ch, g) in groupby(s):
		arr.append(len(list(g)))
	n = len(arr)
	if len(arr) == 1:
		ans = 1
	else:
		ans = 0
		i = j = 0
		while i < n:
			j = max(i, j)
			while j < n and arr[j] <= 1:
				j += 1
			if j == n:
				i += 2
				ans += 1
				if i >= n:
					break
			else:
				arr[j] -= 1
				i += 1
				ans += 1
	print(ans)


import time, math as mt, bisect, sys
from sys import stdin, stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi = 3.141592653589793

def II():
	return int(stdin.readline())

def IO():
	return stdin.readline()

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def P(x):
	return stdout.write(str(x) + '\n')

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

def lcm(a, b):
	return a * b // gcd(a, b)

def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(a % b, b)
	else:
		return gcd(a, b % a)

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count
mx = 10 ** 7
spf = [mx] * (mx + 1)

def SPF():
	spf[1] = 1
	for i in range(2, mx + 1):
		if spf[i] == mx:
			spf[i] = i
			for j in range(i * i, mx + 1, i):
				if i < spf[j]:
					spf[j] = i
	return

def readTree(v):
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = In()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return adj

def solve():
	n = II()
	s = input()
	if n == 1:
		print(1)
		return
	else:
		last = s[0]
		ln = 1
		pref = []
		for i in range(1, n):
			if s[i] != last:
				pref.append(ln)
				last = s[i]
				ln = 1
			else:
				ln += 1
		zz = sum(pref)
		if zz != n:
			pref.append(n - zz)
		op = 0
		xx = len(pref)
		cnt = 0
		last = 0
		for i in range(xx):
			if pref[i] == 1:
				cnt += 1
			else:
				save = cnt
				cnt -= min(cnt, pref[i] - 1)
				op += save - cnt
				pref[i] -= save - cnt
				if pref[i] > 1:
					op += 1
				if cnt > 0 or pref[i] == 1:
					cnt += 1
		if cnt > 0 and cnt % 2:
			op += (cnt + 1) // 2
		elif cnt > 0 and cnt % 2 == 0:
			op += cnt // 2
		print(op)
	return
t = II()
for i in range(t):
	solve()


t = int(input())
M = 2 * 10 ** 5 + 1
import heapq
for _ in range(t):
	n = int(input())
	s = str(input())
	cur = s[0]
	cnt = 0
	X = []
	for i in range(n):
		if s[i] == cur:
			cnt += 1
		else:
			X.append(cnt)
			cur = s[i]
			cnt = 1
	else:
		X.append(cnt)
	X.reverse()
	q = []
	heapq.heapify(q)
	for (i, x) in enumerate(X):
		if x >= 2:
			heapq.heappush(q, (-i, x))
	ans = 0
	while X:
		x = X.pop()
		if x > 1:
			ans += 1
		elif x == 1:
			flag = False
			while q:
				(i, x) = heapq.heappop(q)
				i = -i
				if i >= len(X):
					continue
				else:
					flag = True
					X[i] -= 1
					if x != 2:
						heapq.heappush(q, (-i, x - 1))
					break
			if flag:
				ans += 1
			else:
				ans += 1
				if X:
					X.pop()
		else:
			continue
	print(ans)


import itertools
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	groups = [len(list(g)) for (k, g) in itertools.groupby(s)]
	large_pos = 0
	cur_pos = 0
	count = 0
	while cur_pos < len(groups):
		while large_pos < len(groups) and groups[large_pos] == 1:
			large_pos += 1
		if large_pos < len(groups) and groups[large_pos] > 1:
			groups[large_pos] -= 1
		else:
			cur_pos += 1
		cur_pos += 1
		large_pos = max(large_pos, cur_pos)
		count += 1
	print(count)


import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	se = set()
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			se.add(i)
	now = 0
	idx = 0
	ans = 0
	deleted = set()
	while now < n:
		while idx < n:
			if idx < now or idx not in se:
				idx += 1
				continue
			deleted.add(idx)
			idx += 1
			break
		else:
			now += 1
			while now in deleted:
				now += 1
		while now < n - 1:
			nxt = now + 1
			while nxt in deleted:
				nxt += 1
			if s[now] == s[nxt]:
				now = nxt
				continue
			break
		now += 1
		while now in deleted:
			now += 1
		ans += 1
	print(ans)


from collections import deque
from math import ceil
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	prefix = [1] * n
	revPrefix = [1] * n
	for i in range(1, n):
		if s[i] == s[i - 1]:
			prefix[i] = 1 + prefix[i - 1]
	for i in range(n - 2, -1, -1):
		if s[i] == s[i + 1]:
			revPrefix[i] = 1 + revPrefix[i + 1]
	modified = list()
	bank = deque()
	steps = 0
	pos = 0
	for i in range(n):
		if prefix[i] == 1:
			extras = max(0, revPrefix[i] - 2)
			if extras > 0:
				bank.append([pos, extras])
			if revPrefix[i] > 1:
				number = 2
			else:
				number = 1
			for _ in range(number):
				modified.append(int(s[i]))
			pos += number
	revPrefix = [1] * pos
	for i in range(pos - 2, -1, -1):
		if modified[i] == modified[i + 1]:
			revPrefix[i] = 1 + revPrefix[i + 1]
	i = 0
	while i < pos:
		if len(bank) == 0:
			steps += ceil((pos - i) / 2)
			break
		steps += 1
		if revPrefix[i] > 1:
			if bank[0][0] == i:
				_ = bank.popleft()
			i += 2
		else:
			bank[0][1] -= 1
			if bank[0][1] == 0:
				_ = bank.popleft()
			i += 1
	print(steps)


from math import *
from bisect import *
from collections import *
from random import *
from decimal import *
from itertools import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	a = st()
	a = list(a)
	(i, j) = (0, 0)
	lp = n
	mo = 0
	while i < lp:
		fl = 1
		try:
			p = a[i]
			if a[i] == a[i + 1] and i + 1 <= lp - 1:
				fl = 0
				pass
			else:
				while j < lp - 1 and a[j] != a[j + 1]:
					j += 1
				if j != lp - 1 and j < lp and (a[j] == a[j + 1]):
					fl = 1
					a[j] = '2'
					j += 1
				else:
					while lp > 0 and a[lp - 1] == '2':
						lp -= 1
					lp -= 1
		except:
			p = a[i]
			fl = 0
			pass
		while i < lp and (a[i] == p or a[i] == '2'):
			i += 1
		mo += 1
		if fl == 0:
			j = i
	print(mo)


from sys import stdin, stdout
input = stdin.readline
print = lambda x: stdout.write(str(x) + '\n')
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	p = []
	(o, z) = (0, 0)
	for i in s:
		if i == '1':
			if z:
				p.append(z)
				z = 0
			o += 1
		else:
			if o:
				p.append(o)
				o = 0
			z += 1
	if z:
		p.append(z)
	if o:
		p.append(o)
	ans = 0
	j = 0
	f = 1
	i = 0
	while i < len(p):
		while i < len(p) and p[i] == 0:
			i += 1
		if i == len(p):
			break
		if p[i] > 1:
			ans += 1
			i += 1
			continue
		elif f:
			j = max(i + 1, j)
			while j < len(p) and p[j] < 2:
				j += 1
			if j != len(p):
				p[j] -= 1
				ans += 1
				i += 1
				continue
			f = 0
		ones = 0
		for j in p[i:]:
			if j == 1:
				ones += 1
		ans += (ones + 1) // 2
		break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	j = 0
	ll = []
	count = 1
	tt = 0
	while j < n - 1:
		if s[j + 1] == s[j]:
			count += 1
			if j == n - 2:
				ll.append(count)
				tt += count
			j += 1
		else:
			j += 1
			ll.append(count)
			tt += count
			count = 1
	if n - tt > 0:
		ll.append(n - tt)
	zz = 0
	ans = 0
	qq = 0
	count = 0
	i = 0
	j = i + 1
	ttt = len(ll)
	while i < ttt:
		if j == ttt:
			break
		if ll[i] != 1:
			ans += 1
			i += 1
			j = max(i + 1, j)
		elif ll[j] > 1:
			ll[j] -= 1
			ans += 1
			i += 1
			j = max(i + 1, j)
		else:
			j += 1
	ans += (ttt - i) // 2 + (ttt - i) % 2
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().rstrip()
	comp = []
	s = [s[-i - 1] for i in range(n)]
	bi = s.pop()
	L = 1
	while s:
		if s[-1] == bi:
			L += 1
			s.pop()
		else:
			comp.append(L)
			L = 1
			bi = s.pop()
	comp.append(L)
	a = 0
	b = 0
	res = 0
	while a < len(comp):
		if comp[a] != 1:
			comp[a] = 0
			res += 1
			a += 1
		else:
			while b < len(comp):
				if comp[b] >= 2:
					break
				else:
					b += 1
			if b == len(comp):
				comp[a] = 0
				if a + 1 < len(comp):
					comp[a + 1] = 0
					res += 1
					a += 2
				else:
					res += 1
					a += 1
			else:
				comp[b] -= 1
				res += 1
				comp[a] = 0
				a += 1
	print(res)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

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

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def comb(n, r):
	if n < r:
		return 0
	else:
		return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
from collections import defaultdict
sys.setrecursionlimit(300000)

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
from math import factorial as f

def solve():
	for _ in range(N()):
		n = N()
		s = inp()
		ans = 0
		cnt = 1
		for i in range(1, n):
			if s[i] == s[i - 1]:
				ans += 1
				ans = min(ans, cnt)
			else:
				cnt += 1
		ans += (cnt - ans + 1) // 2
		print(ans)
solve()


import sys
import math
from functools import reduce
import bisect

def getN():
	return int(input())

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

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

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

def index(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	return False
from itertools import groupby
for _ in range(getN()):
	n = getN()
	s = input()
	actions = 0
	now = 0
	for (_, p) in groupby(s):
		p = list(p)
		if len(p) == 1:
			now += 1
		elif now >= len(p) - 1:
			now -= len(p) - 2
			actions += len(p) - 1
		else:
			actions += now + 1
			now = min(0, len(p) - 1)
	print(actions + math.ceil(now / 2))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

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

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve(case):
	n = int(inp())
	a = list(inp())
	for i in range(n):
		a[i] = int(a[i])
	a.append(2)
	cnt = []
	prev = a[0]
	curr = 1
	for i in range(1, len(a)):
		if a[i] == prev:
			curr += 1
		else:
			cnt.append(curr)
			curr = 1
			prev = a[i]
	cnt = cnt[::-1]
	ans = 0
	p = len(cnt) - 1
	while cnt:
		ans += 1
		p = min(p, len(cnt) - 1)
		while p >= 0 and cnt[p] == 1:
			p -= 1
		if p >= 0:
			cnt[p] -= 1
		else:
			cnt.pop()
		if cnt:
			cnt.pop()
	print(ans)
testcase(int(inp()))


import math
T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	(zer, on) = (0, 0)
	l = []
	if n <= 2:
		print(1)
	else:
		for i in s:
			if i == '1':
				if zer != 0:
					l.append(zer)
				on += 1
				zer = 0
			else:
				if on != 0:
					l.append(on)
				on = 0
				zer += 1
		if on:
			l.append(on)
		if zer:
			l.append(zer)
		(i, ind) = (0, 0)
		ans = 0
		lim = len(l)
		while i < lim:
			if l[i] >= 2:
				i += 1
			else:
				ind = max(ind, i)
				f = 1
				while ind < lim:
					if l[ind] >= 2:
						l[ind] -= 1
						f = 0
						break
					ind += 1
				if f:
					i += 2
				else:
					i += 1
			ans += 1
		print(ans)


class SegTree:

	def __init__(self, lists, function, basement):
		self.n = len(lists)
		self.K = (self.n - 1).bit_length()
		self.f = function
		self.b = basement
		self.seg = [basement] * (2 ** (self.K + 1) + 1)
		X = 2 ** self.K
		for (i, v) in enumerate(lists):
			self.seg[i + X] = v
		for i in range(X - 1, 0, -1):
			self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

	def update(self, k, value):
		X = 2 ** self.K
		k += X
		self.seg[k] += value
		while k:
			k = k >> 1
			self.seg[k] = self.f(self.seg[k << 1], self.seg[k << 1 | 1])

	def query(self, L, R):
		num = 2 ** self.K
		L += num
		R += num
		vL = self.b
		vR = self.b
		while L < R:
			if L & 1:
				vL = self.f(vL, self.seg[L])
				L += 1
			if R & 1:
				R -= 1
				vR = self.f(self.seg[R], vR)
			L >>= 1
			R >>= 1
		return self.f(vL, vR)

	def find_min_index(self, L, R, X):
		return self.fmi(L, R, X, 1, 0, 2 ** self.K)

	def fMi(self, a, b, x, k, l, r):
		if self.seg[k] < x or r <= a or b <= l:
			return -1
		elif k >= 2 ** self.K:
			return k - 2 ** self.K
		else:
			vr = self.fMi(a, b, x, k << 1 | 1, (l + r) // 2, r)
			if vr != -1:
				return vr
			return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

	def fmi(self, a, b, x, k, l, r):
		if self.seg[k] < x or r <= a or b <= l:
			return -1
		elif k >= 2 ** self.K:
			return k - 2 ** self.K
		else:
			vl = self.fmi(a, b, x, k << 1, l, (l + r) // 2)
			if vl != -1:
				return vl
			return self.fmi(a, b, x, k << 1 | 1, (l + r) // 2, r)

def solve():
	n = int(input())
	s = input() + '#'
	cnt = 0
	que = []
	for i in range(n):
		cnt += 1
		if s[i] != s[i + 1]:
			que.append(cnt)
			cnt = 0
	m = len(que)
	seg = SegTree(que, max, 0)
	res = m
	for i in range(m):
		V = seg.query(i, m)
		if V == 1:
			res -= (m - i) // 2
			break
		else:
			p = seg.find_min_index(i, m, 2)
			seg.update(p, -1)
	print(res)
	return

def main():
	t = int(input())
	for i in range(t):
		solve()
	return
main()


(z, zz) = (input, lambda : list(map(int, z().split())))
zzz = lambda : [int(i) for i in stdin.readline().split()]
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))
from string import *
from re import *
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f
from bisect import bisect as bs
from bisect import bisect_left as bsl
from itertools import accumulate as ac

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def prime(x):
	p = ceil(x ** 0.5) + 1
	for i in range(2, p):
		if x % i == 0 and x != 2 or x == 0:
			return 0
	return 1

def dfs(u, visit, graph):
	visit[u] = True
	for i in graph[u]:
		if not visit[i]:
			dfs(i, visit, graph)
num = int(z())
for _ in range(num):
	n = int(z())
	lst = z()
	arr = []
	ans = 1
	for i in range(n - 1):
		if lst[i] == lst[i + 1]:
			ans += 1
		else:
			arr.append(ans)
			ans = 1
	arr.append(ans)
	ans = 0
	l = len(arr)
	for i in range(l):
		ans = min(ans + arr[i] - 1, i + 1)
	ans = ans + ceil((l - ans) / 2)
	print(ans)


T = int(input())
for _ in range(0, T):
	n = int(input())
	s = input()
	now = 0
	dq = list()
	while now < n:
		x = s[now]
		cnt = 0
		while now < n and s[now] == x:
			cnt = cnt + 1
			now = now + 1
		dq.append(cnt)
	deleted = 0
	ans = 0
	for cnt2 in dq:
		if cnt2 == 1:
			deleted = deleted + 1
		elif cnt2 > 2:
			deleted = deleted - min(deleted, cnt2 - 2)
		ans = ans + 1
	print(ans - deleted // 2)


import collections
t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip(' ')
	d = collections.deque()
	k = 1
	pre = s[0]
	for i in range(1, n):
		if pre != s[i]:
			d.append(k)
			k = 1
			pre = s[i]
		else:
			k += 1
	d.append(k)
	count = 0
	k = n
	while d:
		if d[0] > 1:
			count += 1
			d.popleft()
			continue
		dn = len(d)
		if k > dn or d[-k] == 1:
			if k > dn:
				k = dn
			while k > 0 and d[-k] == 1:
				k -= 1
			if k == 0:
				count += dn // 2 + dn % 2
				break
		d.popleft()
		count += 1
		d[-k] -= 1
	print(count)


def answer(n, A):
	count = 1
	dp = []
	for i in range(0, n - 1):
		if A[i] == A[i + 1]:
			count += 1
		else:
			dp.append(count)
			count = 1
	dp.append(count)
	i = 0
	j = 0
	count = 0
	while i < len(dp):
		if dp[i] > 1:
			dp[i] = 0
			count += 1
			i += 1
		else:
			j = max(i + 1, j)
			while j < len(dp) and dp[j] == 1:
				j += 1
			if j == len(dp):
				count += (j - i + 1) // 2
				break
			else:
				dp[j] -= 1
				count += 1
				i += 1
	return count
t = int(input())
for i in range(t):
	n = int(input())
	A = input()
	print(answer(n, A))


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	if n == 1:
		print(1)
		continue
	renzoku = []
	ren = 1
	for i in range(1, n):
		if s[i - 1] == s[i]:
			ren += 1
		else:
			renzoku.append(ren)
			ren = 1
		if i == n - 1:
			renzoku.append(ren)
	pena = 0
	count = 0
	l = len(renzoku)
	for i in range(l):
		count += renzoku[i] - 1
		if count > i + 1:
			pena += count - (i + 1)
			count = i + 1
	ans = (n - pena + 1) // 2
	print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()

def RLE(s):
	cc = []
	ww = []
	pc = s[0]
	w = 0
	for c in s:
		if c == pc:
			w += 1
		else:
			cc.append(pc)
			ww.append(w)
			w = 1
			pc = c
	cc.append(pc)
	ww.append(w)
	return (cc, ww)
for _ in range(II()):
	n = II()
	s = SI()
	(cc, ww) = RLE(s)
	ans = 0
	j = 0
	back = False
	for i in range(len(ww)):
		w = ww[i]
		if w == 0:
			break
		if back:
			j -= 1
			ww[j] = 0
		else:
			if j < i:
				j = i
			while j < len(ww) and ww[j] == 1:
				j += 1
			if j == len(ww):
				back = True
				j -= 1
				ww[j] = 0
			else:
				ww[j] -= 1
		ans += 1
	print(ans)


from sys import stdin
casos = int(stdin.readline().strip())
c = 1
for caso in range(casos):
	c += 1
	n = int(stdin.readline().strip())
	s = stdin.readline().strip()
	n = len(s)
	d = 0
	l = 0
	ans = 0
	for i in range(n):
		ans += 1
		d += 1
		res = n - (l + 1)
		if d >= res:
			break
		y = l + 1
		while y < n and s[y] == s[l] and (d > 0):
			d -= 1
			y += 1
		y = l
		while y < n and s[y] == s[l]:
			y += 1
		l = y
		if l == n:
			break
	print(ans)


import sys
import math
from collections import defaultdict, deque
input = sys.stdin.readline

def inar():
	return [int(el) for el in input().split()]

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		st = input().strip()
		count = 0
		check = ''
		ans = 0
		minus = 0
		for i in range(n):
			if i == 0:
				check = st[i]
				count += 1
				continue
			if st[i] == check:
				count += 1
			elif count > 1:
				rem = count - 2
				minus = max(0, minus - rem)
				ans += 1
				check = st[i]
				count = 1
			else:
				ans += 1
				minus += 1
				check = st[i]
				count = 1
		if count > 1:
			rem = count - 2
			minus = max(0, minus - rem)
			ans += 1
			check = st[i]
			count = 1
		else:
			ans += 1
			minus += 1
			check = st[i]
			count = 1
		target = math.floor(minus / 2)
		print(ans - target)
main()


t = int(input())
for p in range(t):
	n = int(input())
	s = input()
	b = []
	for j in s:
		b.append(int(j))
	ind = []
	j = 0
	while j < n:
		if b[j] == 0:
			if j > 0 and b[j - 1] != 0:
				ind.append(l)
				l = 1
			elif j > 0 and b[j - 1] == 0:
				l += 1
			elif j == 0:
				l = 1
		elif j > 0 and b[j - 1] != 1:
			ind.append(l)
			l = 1
		elif j > 0 and b[j - 1] == 1:
			l += 1
		elif j == 0:
			l = 1
		j += 1
	ind.append(l)
	j = 0
	i = 0
	ans = 0
	l = len(ind)
	while j < l:
		i = max(i, j)
		while i < l:
			if ind[i] > 1:
				break
			i += 1
		if i == l:
			ans += 1
			j += 2
		else:
			ans += 1
			ind[i] -= 1
			j += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	(one, zero) = (0, 0)
	l = []
	for i in range(n):
		if s[i] == '1':
			if zero != 0:
				l.append(zero)
				zero = 0
			one += 1
		elif s[i] == '0':
			if one != 0:
				l.append(one)
				one = 0
			zero += 1
	if one != 0:
		l.append(one)
	if zero != 0:
		l.append(zero)
	ans = 0
	loan = 0
	m = len(l)
	for i in range(m):
		if l[i] >= 2:
			if loan:
				ans += min(l[i] - 2, loan)
				loan -= min(l[i] - 2, loan)
			ans += 1
		elif l[i] == 1:
			loan += 1
	print(ans + (loan + 1) // 2)


n_inputs = int(input())
for _ in range(n_inputs):
	str_len = int(input())
	str_input = input()
	arr_of_lens = []
	i = 0
	while i < str_len:
		curr_len = 0
		current_char = str_input[i]
		while i < str_len and current_char == str_input[i]:
			curr_len += 1
			i += 1
		arr_of_lens += [curr_len]
	n_lens = len(arr_of_lens)
	first_step_ind = 0
	second_step_ind = 0
	iters = 0
	while first_step_ind < n_lens:
		while first_step_ind < n_lens and arr_of_lens[first_step_ind] <= 1:
			first_step_ind += 1
		if first_step_ind < n_lens:
			arr_of_lens[first_step_ind] -= 1
			arr_of_lens[second_step_ind] = 0
			second_step_ind += 1
			iters += 1
		else:
			iters += (first_step_ind - second_step_ind + 1) // 2
	print(iters)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	s = input()
	pre = -1
	curr = 0
	ls = deque([])
	res = 0
	for i in range(n):
		if pre != s[i]:
			if curr:
				ls.append(curr)
			curr = 1
			pre = s[i]
		else:
			curr += 1
	if curr:
		ls.append(curr)
	while ls and ls[0] > 1:
		res += 1
		ls.popleft()
	ln = len(ls)
	l = 0
	r = 0
	while r < ln:
		if ls[r] > 1:
			take = min(r - l, ls[r] - 1)
			res += take
			ls[r] -= take
			l += take
			if ls[r] > 1:
				res += 1
				r += 1
				l = r
		else:
			r += 1
	res += (r - l + 1) // 2
	print(res)


import sys
import math
import random
input = sys.stdin.readline
T = int(input())
for t in range(T):
	N = int(input())
	S = input()
	size = 1
	A = []
	for i in range(1, N):
		if S[i] == S[i - 1]:
			size += 1
		else:
			A.append(size)
			size = 1
	A.append(size)
	i = 0
	j = 0
	ans = 0
	while i < len(A):
		while j < i or (j + 1 < len(A) and A[j] == 1):
			j += 1
		A[j] -= 1
		A[i] = 0
		if j == len(A) - 1 and A[j] == 0:
			A.pop()
			j -= 1
		i += 1
		ans += 1
	print(ans)


def find_next_scylla_target(scylla, n, s):
	for i in range(scylla + 1, n):
		if s[i] == s[i - 1]:
			return i
	return -1

def find_next_charybdis_target(charybdis, n, s):
	current = s[charybdis]
	for i in range(charybdis + 1, n):
		if s[i] != current:
			return i
	return -1

def find_last_group(n, s):
	for i in range(n - 2, -1, -1):
		if s[i] != s[i + 1]:
			return i
	return n - 1

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = list(input())
		scylla = charybdis = operations = 0
		last_group = find_last_group(n, s)
		scylla_l = []
		scylla_z = 1
		while True:
			operations += 1
			if scylla == -1:
				while scylla_z <= len(scylla_l) and scylla_l[-scylla_z] == n - 1:
					scylla_z += 1
					n -= 1
				n -= 1
			else:
				next_scylla = find_next_scylla_target(scylla, n, s)
				if next_scylla == -1 or next_scylla > last_group:
					scylla = -1
					n -= 1
				else:
					scylla_l.append(next_scylla)
					scylla = next_scylla
			next_charybdis = find_next_charybdis_target(charybdis, n, s)
			if next_charybdis == -1:
				break
			else:
				charybdis = next_charybdis
			if charybdis > scylla and scylla != -1:
				scylla = charybdis
		print(operations)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s = list(s)
	ans = []
	cnt = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cnt += 1
		else:
			ans.append(cnt)
			cnt = 1
	ans.append(cnt)
	one = 0
	gre = 0
	two = 0
	i = 0
	cnt = 0
	while i < len(ans):
		if ans[i] == 1:
			one += 1
		elif ans[i] == 2:
			cnt += 1
		elif one >= 1:
			x = min(ans[i] - 1, one)
			cnt += x
			one -= x
			ans[i] -= x
			i -= 1
		else:
			cnt += 1
		i += 1
	if one >= 1:
		if one % 2 == 0:
			cnt += one // 2
		else:
			cnt += one // 2 + 1
	print(cnt)


import sys
input = sys.stdin.buffer.readline
T = int(input())
for testcase in range(T):
	n = int(input())
	s = list(input())
	d = []
	cnt = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cnt += 1
		else:
			d.append(cnt)
			cnt = 1
	d.append(cnt)
	n = len(d)
	res = 0
	pidx = 0
	i = 0
	while i < n:
		if d[i] >= 2:
			res += 1
			i += 1
		else:
			flag = True
			if pidx < i:
				pidx = i
			while pidx < n:
				if d[pidx] >= 2:
					d[pidx] -= 1
					flag = False
					break
				else:
					pidx += 1
			if flag:
				res += 1
				i += 2
			else:
				res += 1
				i += 1
	print(res)


TC = int(input())
for tc in range(TC):
	N = int(input())
	S = input()
	ln = []
	cs = S[0]
	c = 0
	for s in S:
		if s == cs:
			c += 1
		else:
			ln.append(c)
			c = 1
			cs = s
	ln.append(c)
	result = 0
	pos = 0
	nxt = pos
	while pos < len(ln):
		if nxt == pos:
			while nxt < len(ln) and ln[nxt] == 1:
				nxt += 1
		if ln[pos] == 1:
			if nxt < len(ln) and nxt != pos:
				ln[nxt] -= 1
				while nxt < len(ln) and ln[nxt] == 1:
					nxt += 1
			else:
				pos += 1
		else:
			nxt += 1
		pos += 1
		result += 1
	print(result)


import sys, os, io

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

def ri():
	return int(sys.stdin.readline())

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

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	for _ in range(ri()):
		n = ri()
		a = rs() + '2'
		s = 1
		z = []
		for i in range(1, n + 1):
			if a[i] != a[i - 1]:
				z.append(s)
				s = 1
			else:
				s += 1
		op = 0
		st = 0
		lz = len(z)
		while True:
			c = 0
			for i in range(st, lz):
				if z[i] >= 2:
					z[i] -= 1
					n -= 1
					c = 1
					break
			if c == 0:
				op += math.ceil((len(z) - op) / 2)
				break
			else:
				op += 1
				st = max(i, op)
		wi(op)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


def testcase():
	n = int(input())
	s = input()
	fs = []
	last = -1
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			fs.append(i - last)
			last = i
	if last != n - 1:
		fs.append(n - 1 - last)
	m = len(fs)
	ans = 0
	j = 1
	i = 0
	while i < m:
		while j < m and (j <= i or fs[j] <= 1):
			j += 1
		if fs[i] > 1:
			ans += 1
			i += 1
		elif j < m:
			ans += 1
			fs[j] -= 1
			i += 1
			while j < m and fs[j] <= 1:
				j += 1
		else:
			ans += 1
			i += 2
	print(ans)
	return
t = int(input())
for _ in range(t):
	testcase()


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	n = ip()
	s = ips()
	gap = []
	(ct0, ct1) = (0, 0)
	for i in range(n):
		if s[i] == '1':
			ct1 += 1
			if ct0 != 0:
				gap.append(ct0)
				ct0 = 0
		else:
			ct0 += 1
			if ct1 != 0:
				gap.append(ct1)
				ct1 = 0
	if ct0 != 0:
		gap.append(ct0)
	if ct1 != 0:
		gap.append(ct1)
	ans = 0
	great = deque()
	nn = len(gap)
	for i in range(nn):
		if gap[i] > 1:
			great.append([gap[i], i])
	i = 0
	while i < nn:
		if len(great) == 0:
			i += 2
			ans += 1
		else:
			(ele, pos) = great[0]
			if ele == 1:
				great.popleft()
				if len(great) == 0:
					i += 2
					ans += 1
				else:
					i += 1
					ele -= 1
					great[0] = list([ele, pos])
					ans += 1
			elif pos < i:
				great.popleft()
				if len(great) == 0:
					i += 2
					ans += 1
				else:
					i += 1
					ele -= 1
					great[0] = list([ele, pos])
					ans += 1
			elif pos == i:
				great.popleft()
				i += 1
				ans += 1
			else:
				i += 1
				ele -= 1
				if ele == 1:
					great.popleft()
				else:
					great[0] = list([ele, pos])
				ans += 1
	out(ans)


class Solution:

	def __init__(self, n, str):
		self.ans = 0
		self.n = n
		self.str = str
		self.cnt = []
		for (idx, s) in enumerate(self.str):
			if idx == 0 or self.str[idx - 1] != s:
				self.cnt.append(1)
			else:
				self.cnt[-1] += 1

	def solve(self):
		pos = -1
		for (idx, l) in enumerate(self.cnt):
			if l != 1:
				pos = idx
				break
		if pos == -1:
			return (len(self.cnt) + 1) // 2
		start = 0
		while pos < len(self.cnt):
			if self.cnt[pos] == 1:
				while True:
					pos += 1
					if pos == len(self.cnt):
						break
					if self.cnt[pos] != 1:
						break
				if pos == len(self.cnt):
					break
			start += 1
			self.cnt[pos] -= 1
			self.ans += 1
			pos = max(start, pos)
		return self.ans + (len(self.cnt) - start + 1) // 2
t = int(input())
for _ in range(t):
	n = int(input())
	str = input()
	s = Solution(n, str)
	print(s.solve())


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(i, c) = (0, 0)
	visit = [-1 for _ in range(n)]
	(flag, last) = (0, -1)
	while i < n:
		if visit[i] == 1:
			i += 1
			continue
		if i + 1 < n and s[i] == s[i + 1]:
			c += 1
			while i + 1 < n and s[i] == s[i + 1]:
				i += 1
			i += 1
		elif i == n - 1:
			i += 1
			c += 1
		else:
			c += 1
			if flag == 1:
				c1 = 1
				j = i + 1
				while j < n:
					if visit[j] == -1:
						visit[j] = 1
						c1 -= 1
						break
					j += 1
				i = j + 1
				continue
			if last == -1:
				j = i + 1
			else:
				j = max(i + 1, last + 1)
			while j < n and visit[j] == 1 or (j + 1 < n and s[j] != s[j + 1]):
				j += 1
			if j < n:
				visit[j] = 1
				i += 1
				last = j
			else:
				flag = 1
				c1 = 1
				j = i + 1
				while j < n:
					if visit[j] == -1:
						visit[j] = 1
						c1 -= 1
						break
					j += 1
				i = j + 1
	print(c)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, list(input())))
	num = []
	temp = 1
	n1 = 0
	for i in range(1, n):
		if a[i] == a[i - 1]:
			temp += 1
		else:
			num.append(temp)
			n1 += 1
			temp = 1
	num.append(temp)
	n1 += 1
	i = 0
	j = 0
	moves = 0
	while j < n1 and i <= j:
		if num[j] > 1:
			moves += 1
			i += 1
			num[j] -= 1
			if i > j:
				j += 1
		else:
			while j < n1 and num[j] == 1:
				j += 1
	left = j - i
	moves += int(ceil(left / 2))
	print(moves)


import sys, bisect, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range
R = range

def Golf():
	(n, *t) = map(int, open(0).read().split())

def I():
	return int(input())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

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

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def NLI(n):
	return [[int(i) for i in input().split()] for i in range(n)]

def NLI_(n):
	return [[int(i) - 1 for i in input().split()] for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RA():
	return map(int, open(0).read().split())

def RLI(n=8, a=1, b=10):
	return [random.randint(a, b) for i in range(n)]

def RI(a=1, b=10):
	return random.randint(a, b)

def INP():
	N = 10
	A = 10
	n = random.randint(1, N)
	a = [random.randint(1, A) for i in range(n)]
	return (n, a)

def Rtest(T):
	(case, err) = (0, 0)
	for i in range(T):
		inp = INP()
		a1 = naive(*inp)
		a2 = solve(*inp)
		if a1 != a2:
			print((a1, a2), inp)
			err += 1
		case += 1
	print('Tested', case, 'case with', err, 'errors')

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
l_alp = string.ascii_lowercase
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()

class UnionFind:

	def __init__(self, n):
		self.table = [-1] * n

	def _root(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self._root(self.table[x])
			return self.table[x]

	def find(self, x, y):
		return self._root(x) == self._root(y)

	def union(self, x, y):
		r1 = self._root(x)
		r2 = self._root(y)
		if r1 == r2:
			return
		d1 = self.table[r1]
		d2 = self.table[r2]
		if d1 <= d2:
			self.table[r2] = r1
			if d1 == d2:
				self.table[r1] -= 1
		else:
			self.table[r1] = r2

	def __str__(self):
		rt = [i if j < 0 else j for (i, j) in enumerate(self.table)]
		return str(rt)
show_flg = False
show_flg = True
ans = 0
for _ in range(I()):
	n = I()
	s = [int(i) for i in input()]
	q = []
	p = s[0]
	k = 1
	for i in range(1, n):
		if s[i] == p:
			k += 1
		else:
			q.append(k)
			k = 1
		p = s[i]
	q.append(k)
	r = 0
	n = len(q)
	c = 0
	l = 0
	while l < n:
		c += 1
		while r + 1 < n and q[r] == 1:
			r += 1
		if q[r] == 1:
			l += 1
		else:
			q[r] -= 1
		l += 1
		if r < l:
			r = l
	print(c)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10

def solve(N, S):
	S += 'x'
	c0 = S[0]
	i0 = 0
	L = []
	M = collections.deque()
	for i in range(N + 1):
		if S[i] != c0:
			l = i - i0
			L.append(l)
			if l > 1:
				M.append(len(L) - 1)
			c0 = S[i]
			i0 = i
	n = 0
	i = 0
	while i < len(L):
		if L[i] == 1:
			done = False
			while M:
				k = M.popleft()
				if i <= k:
					L[k] -= 1
					if L[k] > 1:
						M.appendleft(k)
					i += 1
					done = True
					break
			if not done:
				i += 2
		else:
			i += 1
		n += 1
	return n
T0 = int(input())
for _ in range(T0):
	N = int(input())
	S = input()
	print(solve(N, S))


t = int(input())
for case in range(t):
	n = int(input())
	s = input()
	groups = [s[0]]
	for x in s[1:]:
		if x == groups[-1][-1]:
			groups[-1] += x
		else:
			groups.append(x)
	groups = [len(x) for x in groups]
	to_use = 0
	ops = 0
	for (i, x) in enumerate(groups):
		while to_use < len(groups):
			if to_use < i:
				to_use += 1
				continue
			if groups[to_use] <= 1:
				to_use += 1
				continue
			break
		else:
			break
		groups[to_use] -= 1
		groups[i] = 0
		ops += 1
	else:
		print(ops)
		continue
	size = len(groups) - i
	ops += (size + 1) // 2
	print(ops)


import math
for _ in range(int(input())):
	int(input())
	arr = list(map(int, list(input()))) + ['$']
	n = len(arr)
	ans = 0
	l = arr[0]
	tot = 0
	ones = 0
	for i in range(n):
		if arr[i] == l:
			tot += 1
		else:
			if tot == 1:
				ones += 1
			else:
				m = 1
				if i == n - 1:
					m = 0
				minus = min(ones, tot - m)
				ans += minus
				tot -= minus
				ones -= minus
				if tot > 1:
					ans += 1
				elif tot == 1:
					ones += 1
			l = arr[i]
			tot = 1
	print(math.ceil(ones / 2) + ans)


import heapq as hp
for _ in range(int(input())):
	n = int(input())
	a = list(input())
	ans = 0
	cnt = []
	a += ['$']
	temp = 1
	arr = []
	for i in range(n):
		if a[i] != a[i + 1]:
			cnt.append(temp)
			temp = 1
		else:
			temp += 1
	ind = 1
	cur = cnt[:]
	N = len(cur)
	for i in range(N):
		if cur[i] > 1:
			ans += 1
			ind = max(ind, i + 1)
		else:
			find = False
			while ind < N:
				if cur[ind] > 1:
					cur[ind] -= 1
					ans += 1
					find = True
					break
				else:
					ind += 1
			if find == False:
				ans += (N - i + 1) // 2
				break
	print(ans)


import sys
inp = sys.stdin.buffer.readline
inar = lambda : list(map(int, inp().split()))
inin = lambda : int(inp())
inst = lambda : inp().decode().strip()
wrt = sys.stdout.write
pr = lambda *args, end='\n': wrt(' '.join([str(x) for x in args]) + end)
enum = enumerate
inf = float('inf')
cdiv = lambda x, y: -(-x // y)
from heapq import *
_T_ = inin()
for _t_ in range(_T_):
	n = inin()
	s = inst()
	a = []
	prev = '#'
	cnt = 0
	for i in s:
		if i == prev:
			cnt += 1
		else:
			a.append(cnt)
			cnt = 1
		prev = i
	a.append(cnt)
	a = a[1:]
	n = len(a)
	a.append(inf)
	takeout = 0
	sol = 0
	for i in range(n):
		takeout = max(takeout, i)
		while a[takeout] == 1:
			takeout += 1
		a[takeout] -= 1
		if a[takeout] != inf:
			sol += 1
		sol += 1
	pr(cdiv(sol, 2))


for _ in range(int(input())):
	input()
	s = input()
	n = len(s)
	ans = 0
	i = 0
	j = 0
	no = [False] * n
	while i < n:
		if i + 1 == n:
			ans += 1
			break
		if s[i] != s[i + 1]:
			j = max(j, i + 1)
			while j + 1 < n:
				if s[j] == s[j + 1]:
					no[j] = True
					j += 1
					break
				j += 1
			else:
				ans += (n - i - sum(no[i:]) + 1) // 2
				break
		c = s[i]
		i += 1
		while i < n and (s[i] == c or no[i]):
			i += 1
		ans += 1
	print(ans, flush=False)


def ss(n, s):
	if n == 1:
		return 1
	d = {}
	i = 0
	j = 0
	ans = 0
	while i < n:
		while j + 1 < n and s[j] != s[j + 1]:
			j += 1
		if j >= n - 1:
			i += 1
			while i in d:
				i += 1
			i += 1
			while i in d:
				i += 1
		else:
			d[j] = 1
			x = s[i]
			i += 1
			while i in d or (i < n and s[i] == x):
				i += 1
		ans += 1
		j = max(i, j + 1)
	return ans
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	print(ss(n, s))


t = int(input())

def constructPartitions(partition):
	start = 0
	for end in range(1, n):
		if s[end] != s[start]:
			size = end - start
			partition.append(size)
			start = end
	size = n - start
	partition.append(size)

def solve(partition):
	prefixPtr = greaterThanOnePtr = 0
	length = len(partition)
	ans = 0
	while prefixPtr < length:
		while greaterThanOnePtr < length and partition[greaterThanOnePtr] == 1:
			greaterThanOnePtr += 1
		if greaterThanOnePtr != length and partition[greaterThanOnePtr] > 1:
			partition[greaterThanOnePtr] -= 1
			prefixPtr += 1
			if prefixPtr == greaterThanOnePtr + 1:
				greaterThanOnePtr += 1
		elif greaterThanOnePtr == length:
			prefixPtr += 2
		ans += 1
	return ans
for _ in range(t):
	n = int(input())
	s = input()
	if n == 1:
		print(1)
		continue
	partition = list()
	constructPartitions(partition)
	ans = solve(partition)
	print(ans)


T = int(input())
for t in range(T):
	N = int(input())
	s = input()
	groups = []
	current_c = s[0]
	current_count = 0
	for c in s:
		if c == current_c:
			current_count += 1
			continue
		if current_c is not None:
			groups.append(current_count)
			current_count = 1
		current_c = c
	groups.append(current_count)
	i = 0
	im = 0
	moves = 0
	while i < len(groups):
		while im < len(groups) and groups[im] == 1:
			im += 1
		if im >= len(groups):
			left_groups = len(groups) - i
			moves += (left_groups + 1) // 2
			break
		groups[im] -= 1
		i += 1
		im = max(im, i)
		moves += 1
	print(moves)


t = int(input())
for case in range(t):
	n = int(input())
	s = input()
	arr = []
	if n == 1:
		print(1)
		continue
	count = 0
	for i in range(n):
		if i == 0:
			count += 1
		elif i < n - 1:
			if s[i] == s[i - 1]:
				count += 1
			else:
				arr.append(count)
				count = 1
		elif s[i] == s[i - 1]:
			arr.append(count + 1)
		else:
			arr.append(count)
			arr.append(1)
	ans = 0
	i = 0
	j = 0
	m = len(arr)
	while i < m:
		if arr[i] > 1:
			ans += 1
			i += 1
		else:
			while j < m and arr[j] <= 1:
				j += 1
			if j == m:
				ans += (j - i + 1) // 2
				break
			else:
				arr[j] -= 1
				i += 1
				ans += 1
		if i > j:
			j = i
	print(ans)


import sys
import heapq
import copy
import math
import decimal
input = sys.stdin.readline

def binary_exponentiation(a, b):
	ans = 1
	while b != 0:
		bit = b % 2
		if bit == 1:
			ans = ans * a
		a = a * a
		b = b // 2
	return ans

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def insr2():
	s = input()
	s = list(s[:len(s) - 1])
	s = [ord(s[i]) - ord('a') for i in range(len(s))]
	return s

def invr():
	return map(int, input().split())
ans = 0

def pr_list(a):
	print(*a, sep=' ')

def swap(a, b):
	temp = a
	a = b
	b = temp
	return [a, b]

def pri(a, b):
	s = '? ' + str(a) + ' ' + str(b)
	print(s)
	sys.stdout.flush()
result = []

def nCk(arr, itr, k, n):
	if len(arr) == k:
		result.append(arr)
		return
	if len(arr) > k or itr == n + 1:
		return
	nCk(arr + [itr], itr + 1, k, n)
	nCk(arr, itr + 1, k, n)
	return

def nPk(arr, itr, k, n):
	if len(arr) == k:
		result.append(arr)
		return
	if len(arr) > k or itr == n + 1:
		return
	for i in range(len(arr) + 1):
		nPk(arr[0:i] + [itr] + arr[i:len(arr)], itr + 1, k, n)
	nPk(arr, itr + 1, k, n)
	return

def main():
	tests = inp()
	mod = 1000000007
	limit = 10 ** 18
	ans = 0
	stack = []
	arr = []
	heapq.heapify(arr)
	for test in range(tests):
		n = inp()
		s = insr()
		prefix = []
		lenght = 1
		for i in range(1, n):
			if s[i] == s[i - 1]:
				lenght = lenght + 1
			else:
				prefix.append(lenght)
				lenght = 1
		prefix.append(lenght)
		kill = -1
		result = 0
		r = 0
		while True:
			if r == kill:
				r = r + 1
			while r < len(prefix) and prefix[r] == 1:
				r = r + 1
			if r == len(prefix):
				result = result + math.ceil((len(prefix) - 1 - kill) / 2)
				break
			prefix[r] = prefix[r] - 1
			result = result + 1
			kill = kill + 1
		print(result)
main()


from os import path
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 998244353
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('a')

def solve():
	for _ in range(ii()):
		n = ii()
		s = si()
		a = []
		c = 1
		for i in range(1, n):
			if s[i] != s[i - 1]:
				a.append(c)
				c = 1
			else:
				c += 1
		a.append(c)
		n = len(a)
		suf = [0] * n
		x = n
		for i in range(n - 1, -1, -1):
			suf[i] = x
			if a[i] > 1:
				x = i
		ans = 0
		x = suf[0]
		while i < n:
			ans += 1
			x = max(x, suf[i])
			if a[i] > 1:
				i += 1
				continue
			i += 1
			if x >= n:
				i += 1
				continue
			a[x] -= 1
			if a[x] == 1:
				x = suf[x]
		print(ans)
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
solve()


import os
import sys
from io import BytesIO, IOBase
from itertools import groupby

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		a = [[x, len(list(y))] for (x, y) in groupby(s)]
		n = len(a)
		ans = 0
		temp = n - 1
		loca = 0
		for x in range(n):
			if x > temp:
				break
			if a[x][1] > 1:
				ans += 1
				if loca < x + 1:
					loca = x + 1
				continue
			else:
				ans += 1
				chk = 0
				for y in range(loca, temp + 1):
					if a[y][1] > 1:
						a[y][1] -= 1
						loca = y
						chk = 1
						break
				if chk == 0:
					loca = n - 1
					if a[temp][1] == 1:
						a[temp][1] -= 1
						temp -= 1
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for case in range(1, t + 1):
	n = int(input())
	s = input()
	ranges = []
	last_char = s[0]
	last_amount = 1
	for i in range(1, n):
		if s[i] != last_char:
			ranges.append(last_amount)
			last_char = s[i]
			last_amount = 0
		last_amount += 1
	ranges.append(last_amount)
	moves = 0
	pointer = 0
	best_non_1 = 0
	while pointer < len(ranges):
		found = False
		while best_non_1 < len(ranges):
			if ranges[best_non_1] > 1:
				moves += 1
				ranges[best_non_1] -= 1
				pointer += 1
				if best_non_1 < pointer:
					best_non_1 = pointer
				found = True
				break
			best_non_1 += 1
		if not found:
			moves += (len(ranges) - pointer + 1) // 2
			break
	print(moves)


import math
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(100000)

def put():
	return map(int, stdin.readline().split())
for _ in range(int(input())):
	n = int(input())
	s = input()
	l = []
	if s[0] == '1':
		f = 1
	else:
		f = 0
	sm = 0
	for i in range(len(s)):
		if f == 0 and s[i] == '0':
			sm += 1
		elif f == 1 and s[i] == '1':
			sm += 1
		elif f == 0:
			f = 1
			l.append(sm)
			sm = 1
		else:
			f = 0
			l.append(sm)
			sm = 1
	ans = 0
	l.append(sm)
	ind = len(l)
	for i in range(len(l)):
		if l[i] > 1:
			ind = i
			break
	for i in range(len(l)):
		if ind < len(l):
			if l[i] == 1:
				ans += 1
				l[ind] -= 1
				if l[ind] == 1:
					while ind < len(l):
						if l[ind] > 1:
							break
						ind += 1
			else:
				ans += 1
				ind += 1
				while ind < len(l):
					if l[ind] > 1:
						break
					ind += 1
		else:
			ans += (len(l) - i + 1) // 2
			break
	print(ans)


def readis():
	return map(int, input().strip().split())
T = int(input())
while T:
	T -= 1
	n = int(input())
	s = input()
	conts = []
	last = None
	for c in s:
		if c == last:
			conts[-1] += 1
		else:
			conts.append(1)
			last = c
	before = 0
	ops = 0
	for (i, cont) in enumerate(conts):
		before += 1
		if cont > 1:
			_ops = min(before, cont - 1)
			before -= _ops
			ops += _ops
	print(ops + (before + 1) // 2)


for __ in range(int(input())):
	n = int(input())
	ar = list(map(int, input()))
	num = 1
	kek = []
	for i in range(1, n):
		if ar[i] != ar[i - 1]:
			kek.append(num)
			num = 1
		else:
			num += 1
	kek.append(num)
	i = 0
	j = 0
	ans = len(kek)
	lol = len(kek)
	while i < lol:
		while j < len(kek) and kek[j] == 1:
			j += 1
		if j < len(kek):
			kek[j] -= 1
		else:
			lol -= 1
			lol = max(i + 1, lol)
		i += 1
		j = max(j, i)
	ans -= len(kek) - lol
	print(ans)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 1000000007
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(Int()):
	n = Int()
	s = [int(i) for i in input()]
	n = len(s)
	a = []
	c = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			a.append(c)
			c = 1
		else:
			c += 1
	a.append(c)
	ans = 0
	balance = 0
	for i in a:
		if i == 1:
			balance += 1
		else:
			i -= 1
			here = min(balance, i)
			i -= here - 1
			balance -= here
			ans += here
			if i == 1:
				balance += 1
			else:
				ans += 1
	print(ans + Ceil(balance, 2))


for t in range(int(input())):
	n = int(input())
	s = input().strip()
	i = 0
	l = []
	while i < n:
		j = i
		while j < n - 1:
			if s[j] != s[j + 1]:
				break
			j += 1
		l.append(j - i + 1)
		i = j + 1
	m = len(l)
	i = 0
	j = 0
	ans = 0
	while i < m:
		if l[i] > 1:
			ans += 1
			i += 1
		else:
			j = max(j, i + 1)
			while j < m:
				if l[j] > 1:
					break
				j += 1
			if j == m:
				ans += (j - i) // 2 + (j - i) % 2
				i = m
				break
			while l[j] > 1 and l[i] == 1:
				i += 1
				l[j] -= 1
				ans += 1
				if i == m:
					break
	print(ans)


from sys import stdin
stdin.readline

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

def it():
	return int(stdin.readline().strip())
for _ in range(it()):
	n = it()
	s = input()
	(cur, v) = (1, [])
	for i in range(1, n):
		if s[i - 1] == s[i]:
			cur += 1
		else:
			v.append(cur)
			cur = 1
	if cur > 0:
		v.append(cur)
	(i, j, ans) = (0, 0, 0)
	while i < len(v):
		if v[i] > 1:
			ans += 1
			i += 1
		else:
			j = max(i + 1, j)
			ch = 0
			while j < len(v):
				if v[j] > 1:
					v[j] -= 1
					ch = 1
					break
				j += 1
			if ch == 1:
				i += 1
				ans += 1
			else:
				i += 2
				ans += 1
	print(ans)


from __future__ import division
from sys import stdin, stdout
import operator as op
from bisect import *
from itertools import chain, repeat, starmap
from functools import reduce

class SortedList:
	DEFAULT_LOAD_FACTOR = 500

	def __init__(self, iterable=None):
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self.update(iterable)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				_lists[pos - 1].append(value)
				_maxes[pos - 1] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort()
				self.clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]

	def __contains__(self, value):
		_maxes = self._maxes
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def remove(self, value):
		_maxes = self._maxes
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(op.add, zip(head, tail)))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 1 << (len(row1) - 1).bit_length()
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(op.add, zip(head, tail)))
			tree.append(row)
		reduce(list.__iadd__, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self.clear()
				elif self._len <= 8 * (stop - start):
					values = self.__getitem__(slice(None, start))
					if stop < self._len:
						values += self.__getitem__(slice(stop, None))
					self.clear()
					return self.update(values)
			indices = range(start, stop, step)
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(list.__iadd__, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				if start_pos == stop_pos:
					return _lists[start_pos][start_idx:stop_idx]
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(list.__iadd__, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self.__getitem__(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = range(start, stop, step)
			return list((self.__getitem__(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(map(reversed, reversed(self._lists)))

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		pos = bisect_left(self._maxes, value)
		return self._len if pos == len(self._maxes) else self._loc(pos, bisect_left(self._lists[pos], value))

	def bisect_right(self, value):
		pos = bisect_right(self._maxes, value)
		return self._len if pos == len(self._maxes) else self._loc(pos, bisect_right(self._lists[pos], value))
	bisect = bisect_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def copy(self):
		return self.__class__(self)
	__copy__ = copy

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=0, stop=None):
		_len = self._len
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		elif start <= self.bisect_right(value) - 1:
			return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(list.__iadd__, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self.update(other)
		return self

	def __mul__(self, num):
		values = reduce(list.__iadd__, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(list.__iadd__, self._lists, []) * num
		self.clear()
		self.update(values)
		return self

	def __make_cmp(seq_op):

		def comparer(self, other):
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is op.eq:
					return False
				if seq_op is op.ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		comparer.__name__ = '__{0}__'.format(seq_op.__name__)
		return comparer
	__eq__ = __make_cmp(op.eq)
	__ne__ = __make_cmp(op.ne)
	__lt__ = __make_cmp(op.lt)
	__gt__ = __make_cmp(op.gt)
	__le__ = __make_cmp(op.le)
	__ge__ = __make_cmp(op.ge)
	__make_cmp = staticmethod(__make_cmp)

	def __repr__(self):
		return 'SortedList({0})'.format(reduce(list.__iadd__, self._lists, []))
rstr = lambda : stdin.readline().strip()
rint = lambda : int(stdin.readline())
out = []
for _ in range(int(input())):
	(n, s) = (rint(), list(rstr()))
	(cur, flag, rem, twice, ans) = ([0, 0], 1, SortedList(range(n)), 0, 0)
	lst = -1
	while rem:
		if flag:
			flag = 0
			if not twice:
				twice = 1
				for i in range(cur[1], n):
					if i != n - 1 and s[i] == s[i + 1] and (i in rem):
						twice = 0
						cur[1] += 1
						rem.remove(i)
						ans += 1
						break
					cur[1] += 1
			if twice:
				if rem:
					rem.pop(0)
					ans += 1
				else:
					break
		else:
			for i in range(cur[0], n):
				if i in rem:
					if lst == -1 or s[i] == lst:
						lst = s[i]
						rem.pop(0)
					else:
						lst = -1
						flag = 1
						break
				cur[0] += 1
	out.append(ans)
print('\n'.join(map(str, out)))


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	A = []
	prev = '2'
	count = 0
	for i in range(n):
		if s[i] == prev:
			count += 1
		else:
			if count > 0:
				A.append(count)
			prev = s[i]
			count = 1
	A.append(count)
	de = 0
	for i in range(len(A)):
		if A[i] == 1:
			de += 1
		elif A[i] > 2:
			r = A[i] - 2
			de = max(de - r, 0)
	print(len(A) - de // 2)


import io
import os
from collections import Counter, defaultdict, deque

def makeRepeat(arr):
	repeat = [[arr[0], 0]]
	for x in arr:
		if x == repeat[-1][0]:
			repeat[-1][1] += 1
		else:
			repeat.append([x, 1])
	return repeat

def solve(N, S):
	ans = 0
	repeats = makeRepeat(S)
	i = 0
	j = 0
	while i < len(repeats):
		while j < i or (j < len(repeats) and repeats[j][1] == 1):
			j += 1
		if j < len(repeats):
			assert repeats[j][1] > 1
			repeats[j][1] -= 1
			ans += 1
		else:
			ans += 1
			i += 1
		i += 1
	return ans
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	S = input().decode().rstrip()
	ans = solve(N, S)
	print(ans)


import sys
input = sys.stdin.readline
from itertools import groupby

def solveD(s):
	cnt = 0
	xs = [len(list(g)) for (k, g) in groupby(s)]
	ones = 0
	can_save = 0
	for x in xs:
		if x == 1:
			ones += 1
		elif ones == 0:
			cnt += 1
		elif ones == 1:
			ones -= 1
			cnt += 1
			x -= 1
			if x > 1:
				cnt += 1
			else:
				ones += 1
		else:
			while ones and x > 1:
				ones -= 1
				cnt += 1
				x -= 1
			if x == 1:
				ones += 1
			else:
				cnt += 1
	cnt += (ones + 1) // 2
	return cnt
t = int(input())
for _ in range(t):
	input()
	s = input().strip()
	print(solveD(s))


from itertools import groupby

def main():
	N = int(input())
	S = input()
	C = [len(list(x[1])) for x in groupby(S)]
	M = len(C)
	dup_idx = []
	for (i, c) in enumerate(C):
		if c > 1:
			dup_idx.append(i)
	dup_idx.reverse()
	curr = 0
	while dup_idx:
		i = dup_idx[-1]
		if i < curr:
			dup_idx.pop()
			continue
		C[i] -= 1
		if C[i] == 1:
			dup_idx.pop()
		curr += 1
	ans = curr + (M - curr + 1) // 2
	print(ans)

def __starting_point():
	for __ in [0] * int(input()):
		main()
__starting_point()


import math
for _ in range(int(input())):
	(n, s, step1, step2) = (int(input()), [char for char in input().strip()], 0, 1)
	for i in range(1, n):
		if s[i] == s[i - 1]:
			step1 += 1
			step1 = min(step1, step2)
		else:
			step2 += 1
	print(step1 + math.ceil((step2 - step1) / 2))


import sys, math
t = int(input())
for i in range(t):
	n = int(input())
	s = sys.stdin.readline().strip()
	(i, p1, p2, count, c_arr, stack) = (0, 0, 0, 0, [], [])
	while p2 < n:
		while p2 < n and s[p1] == s[p2]:
			p2 += 1
		c_arr.append((p2 - p1, i))
		if p2 - p1 > 2:
			stack.append((p2 - p1, i))
		p1 = p2
		i += 1
	stack.reverse()
	i = 0
	while i < len(c_arr):
		if c_arr[i][0] == 1:
			while len(stack) > 0 and (stack[-1][1] < c_arr[i][1] or stack[-1][0] < 3):
				stack.pop()
			if len(stack) > 0:
				(ptr, l) = (stack[-1][1], stack[-1][0])
				stack[-1] = c_arr[ptr] = (l - 1, ptr)
				i += 1
			elif i + 1 < len(c_arr) and c_arr[i + 1][0] > 1:
				c_arr[i + 1] = (c_arr[i + 1][0] - 1, c_arr[i + 1][1])
				i += 1
			else:
				i += 2
		else:
			i += 1
		count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	i = n - 1
	steps = 0
	bank = 0
	while i >= 0:
		temp = s[i]
		size = 0
		while i >= 0 and s[i] == temp:
			i -= 1
			size += 1
		steps += 1
		bank += size - 1
		if bank == 0 and i == -1:
			break
		if bank == 0:
			i -= 1
		else:
			bank -= 1
	print(steps)


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def get_input(a=str):
	return a(input())

def get_int_input():
	return get_input(int)

def get_input_arr(a):
	return list(map(a, input().split()))

def get_int_input_arr():
	return get_input_arr(int)

def solve():
	t = get_int_input()
	for _ in range(t):
		n = get_int_input()
		string = get_input()
		prefx_group_count = []
		curr = string[0]
		curr_sz = 1
		for i in range(1, len(string)):
			if string[i] != curr:
				curr = string[i]
				prefx_group_count.append(curr_sz)
				curr_sz = 1
			else:
				curr_sz += 1
		prefx_group_count.append(curr_sz)
		left_eligible = 0
		while left_eligible < len(prefx_group_count) and prefx_group_count[left_eligible] <= 1:
			left_eligible += 1
		res = 0
		i = 0
		left_eligible = 0
		while i < len(prefx_group_count):
			res += 1
			while left_eligible < i or (left_eligible < len(prefx_group_count) and prefx_group_count[left_eligible] == 1):
				left_eligible += 1
			if left_eligible < len(prefx_group_count):
				prefx_group_count[left_eligible] -= 1
			else:
				i += 1
			i += 1
		cout << res << endl

def main():
	solve()
main()


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	arr = []
	seq = 1
	for (a, b) in zip(S, S[1:]):
		if a == b:
			seq += 1
		else:
			arr.append(seq)
			seq = 1
	arr.append(seq)
	hist = []
	arr.reverse()
	for (i, a) in enumerate(arr):
		if a == 1:
			continue
		hist.append([i, a])
	ans = 0
	while len(arr):
		if len(hist):
			hist[-1][1] -= 1
			if hist[-1][1] == 1:
				hist.pop()
		elif len(arr):
			arr.pop()
		else:
			break
		ans += 1
		if len(arr):
			arr.pop()
		if len(hist) and hist[-1][0] == len(arr):
			hist.pop()
	print(ans)


import sys
import os
from math import sqrt, log, log2, log10, gcd, floor, pow, sin, cos, tan, pi, inf, factorial
from copy import copy, deepcopy
from sys import exit, stdin, stdout
from collections import Counter, defaultdict, deque
from itertools import permutations
import heapq
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
mod = 1000000007
iinp = lambda : int(sys.stdin.readline())
inp = lambda : sys.stdin.readline().strip()
strl = lambda : list(inp().strip().split(' '))
intl = lambda : list(map(int, inp().split(' ')))
mint = lambda : map(int, inp().split())
flol = lambda : list(map(float, inp().split(' ')))
flush = lambda : stdout.flush()

def permute(nums):

	def fun(arr, nums, cur, v):
		if len(cur) == len(nums):
			arr.append(cur.copy())
		i = 0
		while i < len(nums):
			if v[i]:
				i += 1
				continue
			else:
				cur.append(nums[i])
				v[i] = 1
				fun(arr, nums, cur, v)
				cur.pop()
				v[i] = 0
				i += 1
		return arr
	res = []
	nums.sort()
	v = [0] * len(nums)
	return fun(res, nums, [], v)

def subsets(res, index, arr, cur):
	res.append(cur.copy())
	for i in range(index, len(arr)):
		cur.append(arr[i])
		subsets(res, i + 1, arr, cur)
		cur.pop()
	return res

def sieve(N):
	root = int(sqrt(N))
	primes = [1] * (N + 1)
	(primes[0], primes[1]) = (0, 0)
	for i in range(2, root + 1):
		if primes[i]:
			for j in range(i * i, N + 1, i):
				primes[j] = 0
	return primes

def bs(arr, l, r, x):
	if x < arr[0] or x > arr[len(arr) - 1]:
		return -1
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return -1

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	p = int(sqrt(n))
	for i in range(5, p + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def solve():
	n = iinp()
	s = inp()
	seg = []
	count = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			count += 1
		else:
			seg.append(count)
			count = 1
	seg.append(count)
	ans = 0
	pt = 0
	i = 0
	n = len(seg)
	while i < n:
		while pt < n:
			if seg[pt] > 1:
				seg[pt] -= 1
				break
			pt += 1
		if pt == n:
			i += 1
		while pt <= i:
			pt += 1
		ans += 1
		i += 1
	print(ans)
for _ in range(iinp()):
	solve()


from math import log2

class Sparse:

	def __init__(self, a, func=min):
		self.a = a
		self.n = len(a)
		self.k = int(log2(self.n)) + 1
		self.func = func
		self.lookup = [[0] * self.k for _ in range(self.n)]
		self.process()

	def process(self):
		for i in range(self.n):
			self.lookup[i][0] = self.a[i]
		j = 1
		while 1 << j <= self.n:
			i = 0
			while i + (1 << j) - 1 < self.n:
				self.lookup[i][j] = self.func(self.lookup[i][j - 1], self.lookup[i + (1 << j - 1)][j - 1])
				i += 1
			j += 1

	def query(self, alpha, omega):
		x = int(log2(omega - alpha + 1))
		return self.func(self.lookup[alpha][x], self.lookup[omega - (1 << x) + 1][x])
from math import inf, log2

class SegmentTree:

	def __init__(self, array, func=max):
		self.n = len(array)
		self.size = 2 ** (int(log2(self.n - 1)) + 1) if self.n != 1 else 1
		self.func = func
		self.default = 0 if self.func != min else inf
		self.data = [self.default] * (2 * self.size)
		self.process(array)

	def process(self, array):
		self.data[self.size:self.size + self.n] = array
		for i in range(self.size - 1, -1, -1):
			self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

	def query(self, alpha, omega):
		if alpha == omega:
			return self.data[alpha + self.size]
		res = self.default
		alpha += self.size
		omega += self.size + 1
		while alpha < omega:
			if alpha & 1:
				res = self.func(res, self.data[alpha])
				alpha += 1
			if omega & 1:
				omega -= 1
				res = self.func(res, self.data[omega])
			alpha >>= 1
			omega >>= 1
		return res

	def update(self, index, value):
		index += self.size
		self.data[index] = value
		index >>= 1
		while index:
			self.data[index] = self.func(self.data[2 * index], self.data[2 * index + 1])
			index >>= 1
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from collections import deque
for _ in range(int(input()) if True else 1):
	n = int(input())
	s = list((k for k in input()))
	ans = 0
	a = []
	cur = s[0]
	val = 0
	for i in range(n):
		if s[i] == cur:
			val += 1
		else:
			a += [val]
			val = 1
		cur = s[i]
	a += [val]
	a = deque(a)
	i = 0
	j = 0
	while True:
		if i == len(a):
			break
		while j < len(a) and a[j] <= 1:
			j += 1
		if j < len(a):
			a[j] -= 1
		else:
			a[i] -= 1
		if a[i] == 0:
			i += 1
		if i != len(a):
			a[i] = 0
			i += 1
		ans += 1
	print(ans)


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()[:-1]
	arr = []
	val = s[0]
	c = 0
	for i in s:
		if i == val:
			c += 1
		else:
			arr.append(c)
			c = 1
			val = i
	if c > 0:
		arr.append(c)
	ans = 0
	q = []
	for i in range(len(arr)):
		if arr[i] != 1:
			q.append(i)
	k = 0
	while 1:
		if arr == []:
			break
		if arr[0] > 1:
			ans += 1
			q.pop(0)
			arr.pop(0)
		else:
			if len(q) > 0:
				arr[q[0] - k] -= 1
				if arr[q[0] - k] == 1:
					q.pop(0)
				ans += 1
			else:
				ans += len(arr) // 2 + len(arr) % 2
				break
			arr.pop(0)
		k += 1
	stdout.write(str(ans) + '\n')


for i in range(int(input())):
	x = input()
	s = input()
	a = []
	last = ''
	k = 0
	for i in s:
		if i == last:
			k += 1
		else:
			last = i
			a.append(k)
			k = 1
	if k > 0:
		a.append(k)
	if len(a) <= 2:
		print(1)
	else:
		i = 1
		j = 1
		ss = sum(a)
		while j < len(a) and a[j] == 1:
			j += 1
		k = 1
		if j == len(a):
			j -= 1
			k = -1
		ans = 0
		while ss > 0:
			if k == -1:
				while a[j] == 0:
					j -= 1
				a[j] -= 1
				ss -= 1
				if ss > 0:
					while a[i] == 0:
						i += 1
					ss -= a[i]
					a[i] = 0
			else:
				while j < len(a) and a[j] <= 1:
					j += 1
				if j == len(a):
					j -= 1
					k = -1
				a[j] -= 1
				ss -= 1
				if ss > 0:
					while a[i] == 0:
						i += 1
					ss -= a[i]
					a[i] = 0
			ans += 1
		print(ans)


import sys
import math

def II():
	return int(sys.stdin.readline())

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

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
t = II()
for q in range(t):
	n = II()
	sa = list(SI())
	temp = 0
	d = []
	s = 0
	for i in range(n):
		if i == 0:
			temp += 1
		elif sa[i] == sa[i - 1]:
			temp += 1
		else:
			d.append(temp)
			temp = 1
	d.append(temp)
	l = len(d)
	count = 0
	for i in range(l - 1, -1, -1):
		if d[i] > 1:
			count += d[i] - 2
			d[i] = 2
		elif count > 0:
			count -= 1
			d[i] += 1
	c = d.count(1)
	print(math.ceil(c / 2) + l - c)


for test in range(int(input())):
	n = int(input())
	s = input()
	sl = []
	ko = 0
	c = 1
	prev = s[0]
	for r in s[1:]:
		if r == prev:
			c += 1
		else:
			sl.append(c)
			c = 1
			prev = r
	sl.append(c)
	if len(sl) == 1:
		print(1)
	else:
		res = 1
		z = sl[-1] - 1
		for i in reversed(range(len(sl) - 1)):
			if sl[i] == 1:
				if z > 0:
					res += 1
					z -= 1
				else:
					z += 1
			else:
				res += 1
				z = z + sl[i] - 2
		print(res)


import itertools

def countstrs(s):
	return [(k, len(list(g))) for (k, g) in itertools.groupby(s)]

def do():
	q = int(input())
	for _ in range(q):
		from collections import deque
		n = int(input())
		s = input()
		c = countstrs(s)
		c = map(lambda x: x[1], c)
		c = list(c)
		c = deque(c)
		over2 = []
		for i in range(len(c)):
			x = c[i]
			if x == 1:
				continue
			over2.append([i, x])
		over2 = deque(over2)
		res = 0
		l = 0
		endl = len(c)
		while l < endl:
			res += 1
			used2 = False
			if len(over2) > 0:
				(ind, x) = over2.popleft()
				if ind == l:
					used2 = True
				else:
					used2 = True
					x -= 1
					if x > 1:
						over2.appendleft([ind, x])
			if used2 is False:
				l += 1
			l += 1
		print(res)
do()


import math

def solve(n, s):
	count = 1
	arr = []
	if n == 1:
		arr.append(1)
	for i in range(1, n):
		if i == n - 1:
			if s[i - 1] != s[i]:
				arr.append(count)
				count = 1
				arr.append(count)
				break
			arr.append(count + 1)
			break
		if s[i - 1] != s[i]:
			arr.append(count)
			count = 1
		else:
			count += 1
	j = 0
	for i in range(len(arr)):
		if arr[i] != 1:
			j += min(arr[i] - 1, i - j + 1)
	return j + math.ceil((len(arr) - j) / 2)
t = int(input())
for i in range(t):
	print(solve(int(input()), input()))


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
lcm = lambda x, y: x * y // gcd(x, y)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	n = I()
	cnt = 0
	s = S() + '#'
	a = []
	for i in range(1, n + 1):
		cnt += 1
		if s[i] != s[i - 1]:
			a += (cnt,)
			cnt = 0
	flg = False
	j = 0
	ln = len(a)
	ans = 0
	for i in range(ln):
		if flg:
			flg = False
			continue
		if a[i] > 1:
			a[i] = 0
		else:
			while j < ln and a[j] < 2:
				j += 1
			if j != ln:
				a[j] -= 1
			else:
				flg = True
		ans += 1
	print(ans)


import math

def value():
	return tuple(map(int, input().split()))

def arr():
	return [int(i) for i in input().split()]

def inn():
	return int(input())
for _ in range(inn()):
	n = inn()
	a = [int(x) for x in input()]
	ans = 0
	i = 0
	c = 0
	while i < n:
		if i < n - 1 and a[i] != a[i + 1]:
			a[i] = -1
			i += 1
			c += 1
		elif i < n - 1 and a[i] == a[i + 1]:
			if c > 0:
				a[i] = -1
				i += 1
				c -= 1
			else:
				val = a[i]
				while i < n and a[i] == val:
					a[i] = -1
					i += 1
			ans += 1
		else:
			c += 1
			i += 1
	ans += math.ceil(c / 2)
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	string = input()
	if n == 1:
		print(1)
		continue
	arr = []
	count = 1
	for i in range(n - 1):
		if string[i] == string[i + 1]:
			count += 1
		else:
			arr.append(count)
			count = 1
	if string[-1] == string[-2]:
		arr.append(count)
	else:
		arr.append(1)
	prefix = 0
	waste = 0
	sum = 0
	n = len(arr)
	while waste < n:
		if arr[waste] != 1:
			arr[waste] -= 1
			sum += 1
			prefix += 1
			if prefix > waste:
				waste = prefix
		else:
			waste += 1
	while prefix < n:
		prefix += 2
		sum += 1
	print(sum)


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = []
	c = 0
	last = s[0]
	for i in range(n):
		if s[i] == last:
			c += 1
		else:
			last = s[i]
			count.append(c)
			c = 1
	if c != 0:
		count.append(c)
	tot = []
	for i in range(len(count)):
		if count[i] > 1:
			tot.append(i)
	j = 0
	ans = 0
	i = 0
	while i < len(count):
		if j < len(tot):
			count[tot[j]] -= 1
			if count[tot[j]] == 1:
				j += 1
			elif i == tot[j]:
				j += 1
		else:
			ans += (len(count) - i + 1) // 2
			break
		i += 1
		ans += 1
	print(ans)


import sys

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

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	n = mint()
	s = minp()
	have = [True] * n
	i = 0
	ans = 0
	j = 0
	k = 0
	ks = 0
	kp = 'z'
	left = n
	while True:
		while i < n and (not have[i]):
			i += 1
		if i == n:
			break
		j = max(i, j)
		c = s[i]
		while j < n:
			if have[j] and s[j] != c:
				break
			j += 1
		if k <= i:
			ks = 0
			k = i
			kp = 'z'
		while k < n:
			if have[k]:
				if s[k] != kp:
					ks = 0
					kp = s[k]
					k += 1
				else:
					ks += 1
					break
			else:
				k += 1
		if k == n:
			ans += (left + 1) // 2
			break
		ans += 1
		if have[k]:
			left -= 1
		have[k] = False
		while i < n:
			if have[i] and s[i] != c:
				break
			if have[i]:
				left -= 1
			have[i] = False
			i += 1
	print(ans)

def solve1():
	n = mint()
	s = minp()
	i = 0
	res = 0
	while i < n:
		j = i
		c = s[i]
		while j < n and c == s[j]:
			j += 1
		res += 1
		i = j
for i in range(mint()):
	solve()


from sys import stdin
for _ in range(int(stdin.readline())):
	length = int(stdin.readline())
	string = stdin.readline()
	if length == 1:
		print(1)
		continue
	lists = []
	temp = str(string[0])
	ans = 0
	for i in range(1, length):
		if string[i] != string[i - 1]:
			lists.append(temp)
			temp = ''
			temp += string[i]
		else:
			temp += string[i]
	lists.append(temp)
	total1 = 0
	for x in range(len(lists)):
		i = lists[x]
		if len(i) == 1:
			total1 += 1
		else:
			a = len(i) - 1
			if total1 >= a:
				total1 -= a
				ans += a
				total1 += 1
			else:
				ans += total1 + 1
				total1 = 0
	ans += (total1 + 1) // 2
	print(ans)


gans = []
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, list(input())))
	u = []
	k = 1
	for i in range(1, n):
		if a[i] == a[i - 1]:
			k += 1
		else:
			u.append(k)
			k = 1
	u.append(k)
	dop = 0
	ln = len(u)
	for i in range(ln):
		dop += u[i] - 1
	cur = 0
	ind = 0
	while ind < ln:
		if dop == 0:
			ln -= 1
		else:
			cur += 1
			dop -= 1
		cnt = u[ind] - 1
		if cur < cnt:
			dop -= cnt - cur
			cur = 0
		else:
			cur -= cnt
		ind += 1
	gans.append(ind)
print('\n'.join(map(str, gans)))