You are given a binary string S of length N. 

You have to perform the following operation exactly once:
Select an index i (1 ≤ i ≤ N) and delete S_{i} from S. The remaining parts of S are concatenated in the same order.

How many distinct binary strings of length N-1 can you get after applying this operation?

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

- The first line of input contains a single integer T - the number of test cases. The description of T test cases follow.
- The first line of each test case contains N - the length of the binary string S.
- The second line contains the binary string S.

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

For each test case, output the number of distinct binary strings that you can get after applying the operation exactly once.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
- Sum of $N$ does not exceed $2 \cdot 10^{5}$ over all testcases.

----- Sample Input 1 ------ 
3
3
100
4
1111
5
10110
----- Sample Output 1 ------ 
2
1
4

----- explanation 1 ------ 
Test Case 1: We have $S = 100$. Now, we can get $00$ (on deleting $S_{1}$), $10$ (on deleting $S_{2}$) and $10$ (on deleting $S_{3}$). Therefore, we can get $2$ distinct strings.

Test Case 2: We have $S = 1111$. Now, we will always get $111$ irrespective of the index $i$ on which we apply the operation. Therefore, we can get $1$ distinct string.

Difficulty: EASY
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(0, int(input())):
	x = int(input())
	s = input()
	k = 0
	for i in range(0, len(s) - 1):
		if s[i] == s[i + 1]:
			k = k + 1
	print(x - k)


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


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


for i in range(int(input())):
	t = int(input())
	s = input()
	r = 1
	for i in range(t - 1):
		if s[i] != s[i + 1]:
			r += 1
	print(r)


for i in range(int(input())):
	n = int(input())
	s = input()
	r = 1
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			r += 1
	print(r)


for i in range(int(input())):
	l = int(input())
	s = input()
	result = 1
	for i in range(l - 1):
		if s[i] != s[i + 1]:
			result += 1
		else:
			result += 0
	print(result)


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


for _ in range(int(input())):
	n = int(input())
	s = input()
	distinct = 0
	last = 0
	for i in s:
		if last == 0:
			last = i
			distinct = 1
		elif last != i:
			distinct += 1
			last = i
	print(distinct)


for i in range(int(input())):
	n = int(input())
	x = input()
	count = 0
	for i in range(n - 1):
		if x[i] == x[i + 1]:
			count = count + 1
	print(n - count)


for i in range(int(input())):
	n = int(input())
	s = input()
	t = s.count('01')
	v = s.count('10')
	print(t + v + 1)


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	a = s.count('10')
	b = s.count('01')
	print(a + b + 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	sep_10 = s.count('10')
	sep_01 = s.count('01')
	print(sep_01 + sep_10 + 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	sep_1 = 0
	sep_0 = 0
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			if s[i] == '1':
				sep_1 += 1
			else:
				sep_0 += 1
	print(sep_0 + sep_1 + 1)


for i in range(int(input())):
	n = int(input())
	c = 0
	s = input()
	a = s.count('01')
	b = s.count('10')
	print(a + b + 1)


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	count = 0
	for i in range(n - 2):
		if s[i] == s[i + 1]:
			count = count + 1
	if s[n - 2] == s[-1]:
		count = count + 1
	print(n - count)


for t in range(int(input())):
	n = int(input())
	s = input()
	x = 1
	for i in range(1, len(s)):
		if s[i - 1] != s[i]:
			x += 1
	print(x)


T = int(input())
for i in range(T):
	N = int(input())
	S = list(input())
	c = 1
	for j in range(len(S) - 1):
		if S[j] != S[j + 1]:
			c += 1
	print(c)


k = int(input())
for i in range(k):
	n = int(input())
	s = input()
	temp = 0
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			temp += 1
	print(temp + 1)


for i in range(int(input())):
	n = int(input())
	stri = input()
	num = 0
	for i in range(n - 1):
		if stri[i] == stri[i + 1]:
			num += 1
	print(n - num)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 1
	for i in range(n - 1):
		ans += int(s[i] != s[i + 1])
	print(ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			c += 1
	print(n - c)


t = int(input())
for i in range(0, t):
	n = int(input())
	s = list(input())
	if s == ['1'] * n or s == ['0'] * n:
		print(1)
	else:
		ct = 0
		for j in range(n - 1):
			if s[j] == '1' and s[j + 1] == '1':
				ct += 1
			elif s[j] == '0' and s[j + 1] == '0':
				ct += 1
		print(n - ct)


for _ in range(int(input())):
	n = int(input())
	s = input()
	s2 = s[0]
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			s2 += s[i]
	print(len(s2))


t = int(input())
for t in range(t):
	n = int(input())
	s = input()
	count = 0
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			count += 1
	print(n - count)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = 0
	for x in range(n - 1):
		if s[x] == s[x + 1]:
			a += 1
	print(n - a)


for _ in range(int(input())):
	input()
	s = list(map(str, input()))
	b = None
	if s[0] == '1':
		b = False
	else:
		b = True
	ploy = 1
	for i in s[1:]:
		if b and i == '1':
			b = False
			ploy += 1
		if not b and i == '0':
			b = True
			ploy += 1
	print(ploy)


for _ in range(int(input())):
	n = int(input())
	a = input()
	i = 0
	count = 0
	while i < n - 1:
		if a[i] != a[i + 1]:
			count += 1
		i += 1
	print(max(count + 1, 1))


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


for t in range(int(input())):
	n = int(input())
	s = input()
	df = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			df += 1
	print(n - df)


t = int(input())
for ni in range(t):
	n = int(input())
	s = input()
	l = 0
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			l = l + 1
	print(l + 1)


t = int(input())
while t != 0:
	n = int(input())
	s = input()
	i = 1
	while i < len(s):
		if s[i - 1] == s[i]:
			n = n - 1
		i = i + 1
	print(n)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	groups = 0
	prev = None
	for i in s:
		if prev != i:
			groups += 1
			prev = i
	print(groups)


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


for _ in range(int(input())):
	le = int(input())
	n = input()
	c = 1
	for i in range(1, le):
		if n[i] != n[i - 1]:
			c += 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	y = ''
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			y += s[i]
			y += '#'
		else:
			y += s[i]
	y += s[len(s) - 1]
	x = y.split('#')
	print(len(x))


for t in range(int(input())):
	n = int(input())
	m = input()
	c = 1
	for i in range(n - 1):
		if m[i] != m[i + 1]:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = 1
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			a += 1
	print(a)


for _ in range(int(input())):
	n = int(input())
	s = input()
	z = s.count('0')
	o = s.count('1')
	if z == n or o == n:
		print(1)
	elif z == n - 1 or o == n - 1:
		print(n - 1)
	else:
		c = 0
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				c += 1
		print(n - c)


for i in range(int(input())):
	n = int(input())
	s = input()
	count = 1
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			count += 1
	print(count)


for tc in range(int(input())):
	n = int(input())
	s = input()
	lasti = ''
	cnt = 0
	for i in s:
		if i != lasti:
			cnt += 1
		lasti = i
	print(cnt)


a = int(input(''))
for i in range(a):
	x = int(input(''))
	v = input('')
	l = list(v)
	c = 0
	for j in range(0, len(l) - 1):
		if l[j] != l[j + 1]:
			c = c + 1
	print(c + 1)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	count = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			count += 1
	print(n - count)


for i in range(int(input())):
	N = int(input())
	string = str(input())
	if string.count('1') == N:
		print(1)
	elif string.count('0') == N:
		print(1)
	else:
		count = N
		for x in range(N - 1):
			if string[x] == '1' and string[x + 1] == '1' or (string[x] == '0' and string[x + 1] == '0'):
				count -= 1
		print(count)


for _ in range(int(input())):
	a = int(input())
	b = input()
	c = 0
	for i in range(a - 1):
		if b[i] != b[i + 1]:
			c += 1
	print(c + 1)


for i in range(int(input())):
	n = int(input())
	m = input()
	c = 0
	for i in range(len(m) - 1):
		if m[i] != m[i + 1]:
			c = c + 1
	print(c + 1)


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


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l = [10]
	k = 0
	for i in s:
		if i == '1' and l[-1] != '1':
			l.append('1')
		elif i == '0' and l[-1] != '0':
			l.append('0')
	print(len(l) - 1)


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


p = int(input())
while p:
	n = int(input())
	str = input()
	l = []
	for i in str:
		l.append(i)
	tem = l[0]
	an = []
	const = 0
	for i in range(1, n):
		if l[i] != tem:
			tem = l[i]
			an.append(const + 1)
			const = 0
		else:
			const += 1
	an.append(const + 1)
	p -= 1
	print(len(an))


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	ans = 1
	for j in range(len(s) - 1):
		if s[j] != s[j + 1]:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = 1
	print(s.count('10') + s.count('01') + 1, '\n\n')


for _ in range(int(input())):
	n = int(input())
	s = input()
	b = []
	flag = False
	flg = False
	if s.count('0') == 0 or s.count('1') == 0:
		print(1)
	else:
		for i in s:
			if i == '1':
				if flag == True:
					continue
					flg = False
				else:
					b.append(i)
					flag = True
					flg = False
			elif flg == True:
				continue
				flag = False
			else:
				b.append(i)
				flg = True
				flag = False
		print(len(b))


from bisect import bisect_left, bisect_right
import math
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

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

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	n = ii()
	s = ip()
	arr1 = s.split('0')
	arr2 = s.split('1')
	c = 0
	for i in arr1:
		if len(i) >= 1:
			c += 1
	for j in arr2:
		if len(j) >= 1:
			c += 1
	print(c)