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: interview

Starter code:

Solutions:
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 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)


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)   

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)


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)




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)


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)))
    


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)

        
        
        


import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
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
#from itertools import permutations,combinations
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')
#from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
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)

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)
    #print(a)
    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)

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()
"""
1 2 3 4 5
1 2 4 4
1 2 4
1 3
2
1 2 3 4 5 6
1 2 3 5 5
1 2 3 5
1 2 4
1 3
2
1 2 3 4 5 6 7 ( max, max - 2)
1 2 3 4 6 6 (max - 1, max - 1)
1 2 3 4 6 (max - 1, max - 3)
1 2 3 5 (max - 2 max - 4)
1 2 4
1 3
2
1 2 3 4 5 6 7 8 (6, 8)
1 2 3 4 5 7 7 (7, 7)
1 2 3 4 5 7 (5, 7)
1 2 3 4 6 (4, 6)
1 2 3 5 (3, 5)
1 2 4 (2, 4)
1 3 (1, 3)
2
"""
__starting_point()

t = int(input())

for case in range(t):
    n = int(input())
    s = input()
    #print("Input read in OK", n, s)

    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
    #print("groups are", groups)

    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

        #print("using", to_use)
        groups[to_use] -= 1
        groups[i] = 0
        ops += 1
    else:
        print(ops)
        continue

    # We now have a situation where the grid is of the form 10101010.
    # What do we do? Well,
    # 1010 (even length = n/2)
    # 10101 (odd length = (n + 1)/2)
    # so (n+1)/2 it is
    #print("ops before was", ops)
    size = len(groups) - i
    #print("size is", size)
    ops += (size + 1) // 2
    print(ops)
        
        


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,k = list(map(int, input().split()))
    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
    
    #print(arr)
    
    for i in range(len(arr)):
        limit += 1
        if arr[i] > 1:
            red = arr[i] - 1
            #print(limit)
            gh = min(red, limit)
            arr[i] -= gh
            limit -=gh
            steps += gh
          
    #print(arr, len(arr), steps)
    ans = math.ceil((len(arr) + steps) / 2)
    #
    print(ans)