Kevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length n. Each character of Kevin's string represents Kevin's score on one of the n questions of the olympiad—'1' for a correctly identified cow and '0' otherwise.

However, all is not lost. Kevin is a big proponent of alternative thinking and believes that his score, instead of being the sum of his points, should be the length of the longest alternating subsequence of his string. Here, we define an alternating subsequence of a string as a not-necessarily contiguous subsequence where no two consecutive elements are equal. For example, {0, 1, 0, 1}, {1, 0, 1}, and {1, 0, 1, 0} are alternating sequences, while {1, 0, 0} and {0, 1, 0, 1, 1} are not.

Kevin, being the sneaky little puffball that he is, is willing to hack into the USAICO databases to improve his score. In order to be subtle, he decides that he will flip exactly one substring—that is, take a contiguous non-empty substring of his score and change all '0's in that substring to '1's and vice versa. After such an operation, Kevin wants to know the length of the longest possible alternating subsequence that his string could have.


-----Input-----

The first line contains the number of questions on the olympiad n (1 ≤ n ≤ 100 000).

The following line contains a binary string of length n representing Kevin's results on the USAICO. 


-----Output-----

Output a single integer, the length of the longest possible alternating subsequence that Kevin can create in his string after flipping a single substring.


-----Examples-----
Input
8
10000011

Output
5

Input
2
01

Output
2



-----Note-----

In the first sample, Kevin can flip the bolded substring '10000011' and turn his string into '10011011', which has an alternating subsequence of length 5: '10011011'.

In the second sample, Kevin can flip the entire string and still have the same score.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
def main():
	(n, t, a) = (int(input()), 0, '*')
	for b in input():
		if a == b:
			t += 1
		else:
			a = b
	print(n - max(t - 2, 0))
main()


n = int(input())
s = input()
b = []
k = 1
a0 = s[0]
ma = 0
for i in range(1, n):
	if a0 == s[i] and i == n - 1:
		k += 1
		ma = max(ma, k)
		b.append(k)
	elif a0 == s[i]:
		k += 1
	elif a0 != s[i] and i == n - 1:
		ma = max(ma, k)
		b.append(k)
		b.append(1)
	else:
		ma = max(ma, k)
		b.append(k)
		a0 = s[i]
		k = 1
key = 0
if n == 1:
	key = 1
	print(1)
if ma > 2:
	key = 1
	print(len(b) + 2)
elif key == 0:
	i = 0
	k = 0
	while i < len(b):
		if b[i] > 1:
			k += 1
		if k > 1:
			print(len(b) + 2)
			key = 1
			break
		i += 1
if key == 0:
	if k > 0:
		print(len(b) + 1)
	else:
		print(len(b))


n = int(input())
s = [int(x) for x in list(input().strip())]
an = [s[0]]
c = 0
cq = 0
p = False
q = False
for i in range(1, n):
	if s[i] ^ s[i - 1]:
		an.append(s[i])
		if p == True:
			if i + 1 < n:
				if s[i + 1] == s[i]:
					c += 1
		p = False
	else:
		if p:
			c += 1
		p = True
if True:
	print(min(n, len(an) + 2))


n = int(input())
s = input()
print(min(n, 3 + s.count('01') + s.count('10')))


n = map(int, input().split())
a = input()
(prev, cur) = ('0', '0')
t = 1
flag = 0
x = 1
if len(a) > 1:
	for i in range(len(a)):
		cur = a[i]
		if i > 0:
			if prev == cur:
				x = x + 1
			else:
				x = 1
				t += 1
			if x >= 2:
				flag += 1
		prev = cur
if flag >= 2:
	t += 2
elif flag > 0:
	t += 1
print(int(t))


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	n = nmbr()
	a = [int(ch) for ch in input()]
	n = len(a)
	dp = [[[0 for _ in range(2)] for _ in range(3)] for _ in range(n)]
	dp[0][0][a[0]] = 1
	dp[0][0][1 ^ a[0]] = 0
	dp[0][1][a[0]] = 1
	dp[0][1][1 ^ a[0]] = 1
	dp[0][2][a[0]] = 1
	dp[0][2][1 ^ a[0]] = 1
	for i in range(1, n):
		dp[i][0][a[i]] = max(1 + dp[i - 1][0][1 ^ a[i]], dp[i - 1][0][a[i]])
		dp[i][0][1 ^ a[i]] = 0
		dp[i][1][a[i]] = max(dp[i - 1][0][a[i]], 1 + dp[i - 1][0][1 ^ a[i]])
		dp[i][1][1 ^ a[i]] = max(dp[i - 1][1][a[i]] + 1, dp[i - 1][0][1 ^ a[i]])
		dp[i][2][a[i]] = dp[i - 1][2][1 ^ a[i]] + 1
		dp[i][2][1 ^ a[i]] = dp[i - 1][1][a[i]] + 1
	ans = 0
	for i in range(3):
		for j in range(2):
			ans = max(ans, dp[n - 1][i][j])
	print(ans)


n = int(input())
s = input()
li = [s[0]]
for i in range(1, n):
	if s[i] != li[-1]:
		li.append(s[i])
print(min(n, len(li) + 2))


n = int(input())
s = input()
c = []
cnt = 1
for i in range(1, n):
	if s[i] == s[i - 1]:
		cnt += 1
	else:
		c.append(cnt)
		cnt = 1
c.append(cnt)
ans = len(c)
y = len(c) - c.count(1)
if y >= 2:
	ans += 2
elif y == 1:
	if max(c) >= 3:
		ans += 2
	else:
		ans += 1
print(ans)


def max_score(s):
	a = 0
	p = None
	for c in s:
		if c != p:
			a += 1
		p = c
	return a + min(len(s) - a, 2)
n = int(input())
s = input()
print(max_score(s))


n = int(input())
s = input()
dl = 1
now = s[0]
k = 0
for i in range(1, n):
	if now != s[i]:
		now = s[i]
		dl += 1
for i in range(n - 1):
	if s[i] == s[i + 1] == '0' or s[i] == s[i + 1] == '1':
		k += 1
if k >= 2:
	print(dl + 2)
elif k == 1:
	print(dl + 1)
else:
	print(dl)


n = int(input())
l = input()
cnt = ''
i = 0
from itertools import groupby
for (k, g) in groupby(l):
	cnt += k
cnt = len(cnt)
print(min(cnt + 2, n))


n = int(input())
A = list(map(int, ' '.join(input()).split()))
res = 1
for i in range(1, len(A)):
	if A[i] != A[i - 1]:
		res += 1
print(min(res + 2, n))


def main():
	input()
	(l, a) = ([0, 0], '*')
	for b in input():
		l[a == b] += 1
		a = b
	print(l[0] + min(l[1], 2))

def __starting_point():
	main()
__starting_point()


n = int(input())
b = input()
print(min(n, 3 + sum((x != y for (x, y) in zip(b, b[1:])))))


from sys import stdin
input = stdin.readline
n = int(input())
s = input()
ans = 1
for i in range(1, n):
	if s[i] != s[i - 1]:
		ans += 1
print(min(ans + 2, n))


n = int(input())
a = input()
print(min(n, 3 + a.count('01') + a.count('10')))


n = int(input())
s = [int(x) for x in list(input())]
dp = [0, 0]
dp[s[0]] = 1
for i in range(1, n):
	j = s[i]
	if j == 0:
		x = max(dp[1] + 1, dp[0])
		y = dp[1]
	else:
		x = dp[0]
		y = max(dp[0] + 1, dp[1])
	(dp[0], dp[1]) = (x, y)
ans = max(dp[0], dp[1])
print(min(n, ans + 2))


n = int(input())
s = input()
(k1, k2, k1l, k2l) = (0, 0, '0', '1')
for i in s:
	if k1l != i:
		k1 += 1
		k1l = i
	if k2l != i:
		k2 += 1
		k2l = i
print(min(len(s), max(k1, k2) + 2))


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


n = int(input())
s = str(input())
ret = 3
for i in range(1, n):
	if s[i] != s[i - 1]:
		ret = ret + 1
if ret < n:
	print(ret)
else:
	print(n)


n = int(input())
s = input() + '2'
ans = cur = 1
Max = j = 0
flag = False
cnt2 = 0
for i in range(1, n + 1):
	if s[i] != s[j]:
		j = i
		if s[i] != '2':
			ans += 1
		if cur >= 3:
			flag = True
		elif cur >= 2:
			cnt2 += 1
		cur = 0
	cur += 1
if flag or cnt2 >= 2:
	ans += 2
elif cnt2 == 1:
	ans += 1
print(ans)


def solution():
	n = int(input())
	s = input()
	ans = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans += 1
	print(min(n, ans + 2))
solution()


def non_standard(s):
	result = 1
	for i in range(1, len(s)):
		result += s[i] != s[i - 1]
	return min(result + 2, len(s))
m = int(input())
t = input()
print(non_standard(t))


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


n = int(input())
s = input().strip('\n')
cur = s[0]
l = 1
for i in range(1, n):
	if s[i] != cur:
		l += 1
		cur = s[i]
print(min(l + 2, n))


from math import *
from collections import *
from random import *
from decimal import Decimal
from bisect import *
import sys

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

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

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

def st():
	return input().rstrip('\n')
n = inp()
s = st() + '$'
r = []
co = 0
p = s[0]
for i in range(n + 1):
	if p == s[i]:
		co += 1
	else:
		r.append(co)
		co = 1
		p = s[i]
re = len(r)
fl = 0
for i in range(len(r)):
	if r[i] != 1:
		fl = 2
		break
print(min(n, re + fl))


import itertools as it
import functools
import operator
import collections
import math
import sys

def solve(s, n):
	if n == 1:
		return 1
	alts = sum((a != b for (a, b) in zip(s, s[1:]))) + 1
	lens = [sum((1 for i in iterable)) for (_, iterable) in it.groupby(s)]
	maxlen = max(lens)
	if maxlen == 1:
		return alts
	elif maxlen >= 3:
		return alts + 2
	elif lens.count(2) == 1:
		return alts + 1
	else:
		return alts + 2

def main():
	n = int(input())
	s = input().strip()
	assert len(s) == n
	result = solve(s, n)
	print(result)
main()


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


import sys

def answer(n, s):
	ctr = 0
	cstates = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			ctr += 1
		else:
			cstates += 1
	if ctr >= 2:
		cstates += 2
	elif ctr == 1:
		cstates += 1
	return cstates

def main():
	n = int(sys.stdin.readline())
	s = sys.stdin.readline().rstrip()
	print(answer(n, s))
	return
main()


n = int(input())
a = input()
p = [1] * 4
for i in range(1, n):
	for j in range(2, -1, -1):
		p[j + 1] = max(p[j + 1], p[j] + (a[i - 1] == a[i]))
		p[j] += a[i - 1] != a[i]
print(max(p[0:3]))


x = int(input())
y = input()
if x <= 3:
	print(x)
	quit()
num1 = 0
num0 = 0
for i in y:
	if i == '1':
		num1 = max(num1, num0 + 1)
	else:
		num0 = max(num0, num1 + 1)
maxx = max(num1, num0)
if '11' not in y and '00' not in y:
	print(maxx)
	quit()
print(min(maxx + 2, x))


from __future__ import print_function
from collections import *
from sys import stdin
from math import *
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')
(n,) = gil()
l = []
(zero, one) = ([], [])
for ch in g():
	if l and ch == l[-1][0]:
		l[-1][1] += 1
	else:
		l.append([ch, 1])
for (ch, fi) in l:
	(zero if ch == '0' else one).append(fi)
ans = 0
zero.sort()
one.sort()
dt = 0
if one and one[-1] > 1:
	dt += 1
if zero and zero[-1] > 1:
	dt += 1
if len(one) > 1 and one[-2] > 1:
	dt += 1
if len(zero) > 1 and zero[-2] > 1:
	dt += 1
if one and one[-1] > 2:
	dt = inf
if zero and zero[-1] > 2:
	dt = inf
if dt > 1:
	ans += 2
elif dt:
	ans += 1
print(ans + len(l))


def solve(s, n):
	ans = 1
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			ans += 1
	return min(ans + 2, n)
n = int(input())
s = input()
print(solve(s, n))


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


n = int(input().strip())
a = input()
count_pairs = 0
count_diff = 0
pred = a[0]
for i in range(1, n):
	if a[i - 1] == a[i]:
		count_pairs += 1
	else:
		count_diff += 1
count_pairs = min(count_pairs, 2)
print(count_pairs + count_diff + 1)


n = int(input())
s = input()
k = 0
i = 0
r = int(s[0])
while i < n:
	if int(s[i]) == r:
		r = 1 - r
		k += 1
	i += 1
print(min(k + 2, n))


N = int(input())
S = input()
res = 1
for i in range(1, N):
	res += S[i] != S[i - 1]
print(min(res + 2, N))


n = int(input())
x = input()
q = []
for y in x:
	q.append(int(y))

def get_score(x, y):
	score = 1
	f = q[x]
	for i in range(x + 1, y):
		if q[i] != f:
			score += 1
			f = 1 - f
	return score
flip = 1
for i in range(1, n):
	if flip == 1:
		if q[i] == q[i - 1]:
			flip = 0
			q[i] = 1 - q[i]
	elif flip == 0 and q[i] == q[i - 1]:
		q[i] = 1 - q[i]
	else:
		break
print(get_score(0, n))


__author__ = 'Utena'
n = input()
s = input()
t = []

def alt(a):
	b = ''
	b += a[0]
	for i in a[1:len(a)]:
		if i != b[-1]:
			b += i
	return b
m = len(alt(s))
judge = 0
for i in range(len(s) - 1):
	if s[i + 1] == s[i]:
		judge = 1
		if i < len(s) - 2:
			for j in range(i + 1, len(s) - 1):
				if s[j + 1] == s[j]:
					print(m + 2)
					exit(0)
if judge == 1:
	print(m + 1)
else:
	print(m)


n = int(input())
s = input()
dp = [1] * n
for i in range(1, n):
	if s[i] != s[i - 1]:
		dp[i] = max(dp[i], dp[i - 1] + 1)
	else:
		dp[i] = dp[i - 1]
print(min(n, max(dp) + 2))


n = int(input())
s = input()
curr = s[0]
l = 1
j = 1
while j < n:
	if s[j] != curr:
		l += 1
		curr = s[j]
	j += 1
print(min(l + 2, n))


s1 = int(input())
s2 = input()
d = 1
et = s2[0]
p = 0
tp = '2'
for i in range(1, s1):
	if s2[i] != et:
		d = d + 1
		et = s2[i]
	if s2[i] == s2[i - 1] and tp != s2[i]:
		p = p + 1
if p == 0:
	print(d)
elif p == 1:
	print(d + 1)
else:
	print(d + 2)


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


n = int(input())
s = list(input())
l = []
c = 1
for i in range(1, n):
	if s[i] == s[i - 1]:
		c = c + 1
	else:
		if c >= 2:
			l.append(c)
		c = 1
if c >= 2:
	l.append(c)
inc = 0
if len(l) > 1:
	inc = 2
elif len(l) == 1:
	if l[0] >= 3:
		inc = 2
	elif l[0] == 2:
		inc = 1
(a1, a2) = (0, 0)
c = '1'
for i in range(n):
	if s[i] == c:
		a1 = a1 + 1
		c = '1' if c == '0' else '0'
c = '0'
for i in range(n):
	if s[i] == c:
		a2 = a2 + 1
		c = '0' if c == '1' else '1'
print(max(a1, a2) + inc)


n = int(input())
tab = str(input())
d = 1
tmp = 1
changes = 1
for i in range(1, n):
	if tab[i] != tab[i - 1]:
		changes += 1
print(min(changes + 2, n))


import sys
n = int(input())
s = input()
p = s[0]
ans = 1
for i in range(1, n):
	if s[i] != p:
		ans += 1
		p = s[i]
if 0 <= s.find('00') < s.rfind('00') or 0 <= s.find('11') < s.rfind('11') or 0 <= s.find('11') < s.rfind('00') or (0 <= s.find('00') < s.rfind('11')):
	ans += 2
elif s.find('00') >= 0 or s.find('11') >= 0:
	ans += 1
print(ans)


n = int(input())
s = input()

def solve(n, s):
	if n <= 3:
		return n
	cum = 0
	p = '2'
	count = 0
	for (i, v) in enumerate(s):
		if v != p:
			cum += 1
		else:
			count += 1
		p = v
	if count == 0:
		return cum
	elif count == 1:
		return cum + 1
	else:
		return cum + 2
print(solve(n, s))


nr_of_questions = int(input())
score = list(map(int, input()))
sub_length = 1
for i in range(len(score) - 1):
	if score[i] != score[i + 1]:
		sub_length += 1
sub_length_mod = min(len(score), sub_length + 2)
print(sub_length_mod)


n = int(input())
s = input()
ans = 0
for i in range(1, n):
	if s[i] != s[i - 1]:
		ans += 1
print(min(ans + 3, n))


def solve(n, ar):
	res = 1
	for i in range(n - 1):
		if ar[i] != ar[i + 1]:
			res += 1
	print(min(res + 2, n))
n = int(input())
ar = list(input())
solve(n, ar)


import sys

def solve(n, x):
	ant = x[0]
	cont = 1
	maximo = 1
	maxi = 1
	dos = 0
	for i in range(1, n):
		if ant != x[i]:
			cont += 1
			ant = x[i]
			if maximo >= 2:
				dos += 1
			maximo = 1
		else:
			maximo += 1
		maxi = max(maxi, maximo)
	if maximo >= 2:
		dos += 1
	if maxi >= 3 or dos >= 2:
		return cont + 2
	if dos == 1:
		return cont + 1
	return cont
n = int(input())
x = input()
print(solve(n, x))


(n, s, ans) = (int(input()), list(input()), 1)
flag = 0
for i in range(1, n):
	if s[i] == s[i - 1]:
		s[i] = str(int(s[i]) ^ 1)
		flag = 1
	elif flag:
		break
last = s[0]
for i in s[1:]:
	if i != last:
		last = i
		ans += 1
print(ans)


n = int(input())
a = input()
f = a[0]
if n == 1 or n == 2:
	print(n)
else:
	i = 1
	t1 = 1
	while i < n:
		if a[i] != f:
			f = a[i]
			t1 += 1
		i += 1
	t3 = 0
	t2 = 1
	i = 1
	f1 = 0
	f = a[0]
	q = 0
	while i < n:
		if a[i] == f:
			t2 += 1
			if t2 == 2:
				q = 1
				t3 += 1
				if t3 == 2:
					f1 = 1
					break
			if t2 > 2:
				f1 = 1
				break
		else:
			t2 = 1
			f = a[i]
		i += 1
	if q == 1:
		if f1 == 1:
			print(t1 + 2)
		else:
			print(t1 + 1)
	else:
		print(t1)


n = map(int, input())
s = input()
l = []
cnt = 1
for i in range(1, len(s)):
	if s[i] != s[i - 1]:
		l.append(cnt)
		cnt = 1
	else:
		cnt += 1
l.append(cnt)
result = len(l)
add = 0
if max(l) >= 3:
	add = 2
elif max(l) >= 2:
	add = 1
if len(l) > 1:
	for i in range(1, len(l)):
		if l[i] >= 2 and l[i - 1] >= 2:
			add = 2
	if s[0] != s[len(s) - 1] and l[0] >= 2 and (l[len(l) - 1] >= 2):
		add = 2
	num = 0
	for i in range(0, len(l)):
		if l[i] >= 2:
			num += 1
	if num >= 2:
		add = 2
if add == 0 and (l[0] >= 2 or l[len(l) - 1] >= 2):
	add = 1
print(result + add)


n = int(input())
consec = 1
changes = 0
oppo = 0
rep = False
cons = False
s = input().strip()
prev = s[0]
for x in s[1:]:
	if prev != x:
		changes += 1
		consec = 1
		rep = False
	else:
		consec += 1
		if not rep:
			rep = True
			oppo += 1
	if consec == 3:
		cons = True
	prev = x
if cons or oppo > 1:
	changes += 2
elif oppo == 1:
	changes += 1
print(changes + 1)


import sys

def main():
	n = int(input())
	tab = sys.stdin.readline()
	s = 1
	t = tab[0]
	e = 0
	for i in range(1, len(tab) - 1):
		if t != tab[i]:
			s += 1
			t = tab[i]
		if tab[i] == tab[i - 1] == '0' or tab[i] == tab[i - 1] == '1':
			e += 1
			e = min(e, 2)
	print(s + e)
main()


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


from collections import Counter
_ = input()
s = input().strip()
sequences = Counter()
cur_seq_len = 1
for (p, n) in zip(s, s[1:] + '*'):
	if p == n:
		cur_seq_len += 1
	else:
		if cur_seq_len > 3:
			cur_seq_len = 3
		sequences[cur_seq_len] += 1
		cur_seq_len = 1
basic = sum(sequences.values())
if 3 in sequences or sequences[2] >= 2:
	print(basic + 2)
elif sequences[2] == 1:
	print(basic + 1)
else:
	print(basic)


from sys import stdin
inp = stdin.readline
t = int(inp().strip())
string = list(inp().strip())
longestSub = 1
prev = string[0]
l = 0
d = 0
maxGap = -1
for i in range(1, t):
	if string[i] != prev:
		longestSub += 1
	prev = string[i]
print(min(len(string), longestSub + 2))


n = int(input())
s = list(input())
lis = [0] * n
bb = []
p = s[0]
lis[0] = 1
kk = 0
for i in range(1, len(s)):
	if s[i] != p:
		lis[i] = 1
		p = s[i]
for i in range(1, len(s)):
	if s[i] == s[i - 1]:
		kk += 1
	else:
		bb.append(kk)
		kk = 0
bb.append(kk)
ans = c = 0
if max(bb) > 1:
	print(sum(lis) + 2)
else:
	print(sum(lis) + min(2, bb.count(1)))


import sys
input = sys.stdin.readline
n = int(input())
S = input()[:-1]
(zero, one) = (0, 0)
for Si in S:
	if Si == '0':
		zero = one + 1
	else:
		one = zero + 1
ans = max(zero, one)
s = set()
for i in range(n - 1):
	if S[i] == S[i + 1]:
		s.add(i)
if len(s) >= 2:
	ans += 2
elif len(s) == 1:
	ans += 1
print(ans)


import sys
input_file = sys.stdin
input_file.readline()
bits = list(input_file.readline().rstrip())
num_alt = 1
last_char = bits[0]
if len(bits) <= 3:
	print(len(bits))
	exit()
for (i, char) in enumerate(bits):
	if bits[i] != last_char:
		last_char = bits[i]
		num_alt += 1
if num_alt == len(bits) - 1:
	num_alt += 1
elif num_alt < len(bits) - 1:
	num_alt += 2
print(num_alt)


import sys
import math
MAXNUM = math.inf
MINNUM = -1 * math.inf
ASCIILOWER = 97
ASCIIUPPER = 65

def getInt():
	return int(sys.stdin.readline().rstrip())

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

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

def printOutput(ans):
	sys.stdout.write()
	pass

def solve(string):
	tab = [[0 for _ in range(3)] for _ in range(len(string))]
	states = [[0 for _ in range(3)] for _ in range(len(string))]
	if string[0] == '1':
		states[0][0] = '1'
		states[0][2] = '1'
		states[0][1] = '0'
	else:
		states[0][0] = '0'
		states[0][2] = '0'
		states[0][1] = '1'
	tab[0][0] = 1
	tab[0][1] = 1
	tab[0][2] = 1
	for i in range(1, len(string)):
		ele = string[i]
		if ele != states[i - 1][0]:
			tab[i][0] = tab[i - 1][0] + 1
			states[i][0] = ele
			tab[i][1] = tab[i - 1][0]
		else:
			tab[i][0] = tab[i - 1][0]
			states[i][0] = ele
			tab[i][1] = tab[i - 1][0] + 1
		if ele == states[i - 1][1]:
			tab[i][1] = max(tab[i - 1][1] + 1, tab[i][1])
		states[i][1] = str((int(ele) - 1) % 2)
		if ele != states[i - 1][2]:
			tab[i][2] = tab[i - 1][2] + 1
			states[i][2] = ele
		else:
			tab[i][2] = tab[i - 1][2]
			states[i][2] = ele
		if tab[i][1] > tab[i][2]:
			tab[i][2] = tab[i][1]
			states[i][2] = states[i][1]
	return max(tab[-1])

def readinput():
	a = getInts()
	print(solve(getString()))
readinput()


from sys import stdin

def get_count(c):
	count = 0
	flag = False
	i = 1
	while i < n + 2:
		if arr[i] == arr[i - 1] and arr[i] == c:
			if i == n + 1 or i == n:
				flag = True
			count += 1
			i += 2
			continue
		i += 1
	return (count, flag)
n = int(stdin.readline().strip())
arr = list(map(int, list(stdin.readline().strip())))
aux = [0] * n
aux[0] = 1
for i in range(1, n):
	aux[i] = aux[i - 1]
	if arr[i] != arr[i - 1]:
		aux[i] += 1
count = 0
for i in range(0, n - 1):
	if arr[i] == arr[i + 1]:
		count += 1
count = min(count, 2)
print(aux[-1] + count)


a = int(input())
s = input()
ans = []
count = 1
for i in range(1, len(s)):
	if s[i] == s[i - 1]:
		count += 1
	else:
		ans.append(count)
		count = 1
ans.append(count)
if len(ans) == 1:
	if len(s) == 1:
		print(1)
	if len(s) == 2:
		print(2)
	if len(s) >= 3:
		print(3)
	exit()
r = ans.count(1)
if r == len(ans):
	print(len(ans))
elif r <= len(ans) - 2:
	print(len(ans) + 2)
else:
	temp = max(ans)
	if temp == 2:
		print(len(ans) + 1)
	else:
		print(len(ans) + 2)


n = int(input())
a = list(input())
sum = 0
pr = '2'
for i in range(n):
	if a[i] != pr:
		sum += 1
		pr = a[i]
eo = 0
for i in range(n - 1):
	if a[i] == a[i + 1]:
		eo += 1
if eo >= 2:
	print(min(n, sum + 2))
elif eo == 1 or len(a) == 2:
	print(min(sum + 1, n))
else:
	print(sum)


input()
a = input()
s = []
for c in a:
	if not s or s[-1][0] != c:
		s.append([c, 1])
	else:
		s[-1][1] += 1
s2 = sorted(s, key=lambda x: x[1])
delta = 0
if s2[-1][1] >= 3 or (len(s2) > 1 and s2[-2][1] >= 2):
	delta = 2
elif s2[-1][1] >= 2:
	delta = 1
print(len(s) + delta)


n = int(input())
s = [int(i) for i in input()]
dp = [[0 for _ in range(2)] for _ in range(3)]
for i in range(n):
	x = s[i]
	dp[2][x] = max(dp[2][x], max(dp[2][1 ^ x], dp[1][1 ^ x]) + 1)
	dp[1][1 ^ x] = max(dp[1][1 ^ x], max(dp[1][x], dp[0][x]) + 1)
	dp[0][x] = max(dp[0][x], dp[0][1 ^ x] + 1)
print(max(dp[2][0], dp[2][1]))


from sys import stdin
length = int(stdin.readline().rstrip())
scores = stdin.readline().rstrip()
doubles_found = 0
score = 1
for i in range(length - 1):
	if scores[i] != scores[i + 1]:
		score += 1
	elif doubles_found < 2:
		score += 1
		doubles_found += 1
print(score)


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

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

def lint():
	return [int(x) for x in stdin.readline().split()]

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

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

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

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 1
	right = x
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	if n > 2:
		l.append(n)
	return l
n = I()
s = list(map(int, input().strip()))
(i, cnt) = (0, 0)
tmp = s[0]
ans = 1
for i in range(1, n):
	if s[i] != tmp:
		ans += 1
		tmp = s[i]
print(min(ans + 2, n))


n = int(input())
ch = str(input())
if n == 1:
	print(1)
else:
	B = [0 for _ in range(n)]
	B[0] = 1
	c = ch[0]
	for k in range(1, n):
		if ch[k] == c:
			B[k] = B[k - 1]
		else:
			B[k] = B[k - 1] + 1
			c = ch[k]
	T = [0 for _ in range(n)]
	F = [0 for _ in range(n)]
	T[1] = B[0] + 1
	if ch[1] == ch[0]:
		F[1] = 1
	for i in range(1):
		for j in range(i + 2, n):
			c = 0
			if ch[j] == ch[j - 1] and (not F[j - 1]):
				temp = max([T[j - 1], B[j - 1] + 1])
				if temp == 1 + B[j - 1]:
					c = 1
			else:
				temp = T[j - 1] + 1
				if F[j - 1] and ch[j] != ch[j - 1]:
					c = 1
			T[j] = temp
			F[j] = c
	print(T[n - 1])


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


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	s = list(map(int, input()))
	ans = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans += 1
	print(min(ans + 2, n))
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()


n = int(input())
s = input()
score = 0
count = 0
if n <= 2:
	print(n)
else:
	for i in range(1, n):
		if s[i] != s[i - 1]:
			score += 1
		else:
			count += 1
	print(min(2, count) + score + 1)


n = int(input())
s = input()
(a, j) = (0, 0)
for i in range(len(s)):
	if j % 2 and s[i] == '1':
		a += 1
		j += 1
	elif j % 2 == 0 and s[i] == '0':
		a += 1
		j += 1
(b, j) = (0, 0)
for i in range(len(s)):
	if j % 2 and s[i] == '0':
		b += 1
		j += 1
	elif j % 2 == 0 and s[i] == '1':
		b += 1
		j += 1
count = max(a, b)
print(min(n, count + 2))


input()
s = input()
(t, r) = (int(s[0]), 0)
for i in s:
	if int(i) == t:
		r += 1
		t = 1 - t
print(min(r + 2, len(s)))


n = int(input())
s = input()
mem = s[0]
streak = 1
amount = 0
res = 0
score = 1
for l in range(1, n):
	if s[l] == mem:
		streak += 1
	else:
		mem = s[l]
		streak = 1
		score += 1
	if streak > 2:
		res = 2
	elif streak == 2:
		amount += 1
	if amount > 1:
		res = 2
if amount + max(res - 1, 0) == 1:
	res = 1
print(score + res)


n = int(input())
s = input()
ans = 0
a = 0
b = 0
if s[0] == '0':
	flag = '0'
else:
	flag = '1'
for i in range(n):
	if i > 0 and s[i] == s[i - 1]:
		a += 1
	if s[i] == flag:
		ans += 1
		if flag == '0':
			flag = '1'
		else:
			flag = '0'
ans += min(a + b, 2)
print(ans)


n = int(input())
s = input()
arr = list(map(int, s))
cnt = 0
pcnt = 0
for i in range(n - 1):
	cnt += arr[i] != arr[i + 1]
	pcnt += arr[i] == arr[i + 1]
cnt += min(pcnt, 2)
print(cnt + 1)


n = int(input())
s = list(input())
ans = len([s[i] for i in range(len(s) - 1) if s[i] != s[i + 1]]) + 1
for i in range(n - 1):
	if s[i] == s[i + 1]:
		ans += 1
		break
for j in range(n - 1, 0, -1):
	if j - 1 == i:
		break
	elif s[j] == s[j - 1]:
		ans += 1
		break
print(ans)


import unittest
import sys

class Thinking:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		[self.n] = map(int, uinput().split())
		self.s = uinput()

	def calculate(self):
		result = 1
		empty = 0
		prev = self.s[0]
		for i in range(1, self.n):
			cur = self.s[i]
			if cur != prev:
				result += 1
			else:
				empty += 1
			prev = cur
		result += min(empty, 2)
		return str(result)

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = '8\n10000011'
		d = Thinking(test)
		self.assertEqual(d.n, 8)
		self.assertEqual(d.s, '10000011')
		self.assertEqual(Thinking(test).calculate(), '5')
		test = '2\n01'
		self.assertEqual(Thinking(test).calculate(), '2')
		test = '1\n0'
		self.assertEqual(Thinking(test).calculate(), '1')
		test = '6\n010100'
		self.assertEqual(Thinking(test).calculate(), '6')

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Thinking(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))
sys.setrecursionlimit(100000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
sys.stdout.write(Thinking().calculate())


n = int(input())
s = input()
print(min(n, sum((s[i] != s[i - 1] for i in range(1, n))) + 3))


def answer(n, A):
	count = 1
	for i in range(1, n):
		if A[i] != A[i - 1]:
			count += 1
	return min(count + 2, n)
n = int(input())
s = input()
print(answer(n, s))


def func(a):
	l = []
	for i in a:
		l.append(int(i))
	inc = 1
	dec = 1
	for i in range(1, len(l)):
		if l[i] > l[i - 1]:
			inc = dec + 1
		if l[i] < l[i - 1]:
			dec = inc + 1
	return max(inc, dec)
n = int(input())
l = list(input())
if len(l) == 2:
	print(2)
else:
	ans = 0
	f = 0
	for i in range(len(l) - 1):
		if l[i] == l[i + 1]:
			f = 1
			break
	if f == 1:
		st = i + 1
		while st + 1 < len(l) and l[st] != l[st + 1]:
			st += 1
		range1 = [i + 1, st]
		for p in range(i + 1, st + 1):
			l[p] = 1 - int(l[p])
	print(func(l))


n = int(input().strip())
s = input().strip()
segs = []
start = 0
i = 1
while i <= n:
	if i == n or s[i] != s[start]:
		segs.append(i - start)
		start = i
		i = start + 1
	else:
		i += 1
res = len(segs)
segs.sort()
if segs[-1] >= 3:
	res += 2
elif len(segs) >= 2 and segs[-1] >= 2 and (segs[-2] >= 2):
	res += 2
elif segs[-1] >= 2:
	res += 1
print(res)


n = int(input())
s = input().strip()
ret = 1
nb2 = 0
for i in range(1, n):
	if s[i - 1] != s[i]:
		ret += 1
	else:
		nb2 += 1
if nb2 >= 2:
	ret += 2
else:
	ret += nb2
print(ret)


(n, line) = (int(input()), input())
ans = 1 + sum((line[i] != line[i - 1] for i in range(1, n)))
print(min(ans + 2, n))


import sys
n = int(sys.stdin.readline())
s = sys.stdin.readline()
s = list(s)
a = []
k = 1
for i in range(n):
	if i == n - 1:
		a.append(k)
		break
	if s[i] == s[i + 1]:
		k += 1
	else:
		a.append(k)
		k = 1
add_amount = 0
count = 0
for i in range(n - 1):
	if s[i] == s[i + 1]:
		count += 1
add_amount = min(2, count)
print(len(a) + add_amount)


n = int(input())
s = input()
cnt = 1
intervals = [1]
for i in range(1, n):
	if s[i] != s[i - 1]:
		intervals.append(1)
	else:
		intervals[-1] += 1
has_three = False
for interval in intervals:
	if interval >= 3:
		has_three = True
		break
if has_three:
	print(len(intervals) + 2)
else:
	twos = intervals.count(2)
	if twos >= 2:
		print(len(intervals) + 2)
	elif twos == 1:
		print(len(intervals) + 1)
	else:
		print(len(intervals))


n = int(input())
a = list(input())
start = 0
end = 0
if n == 1:
	print(1)
	exit(0)
for i in range(n - 1):
	if a[i] == a[i + 1]:
		break
if i == n - 2:
	print(n)
	exit(0)
else:
	ans = 0
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			ans += 1
	print(min(n, ans + 3))


bb = input()
aa = input()
seq = [int(aa[x]) for x in range(len(aa))]
seq_rev = [~x % 2 for x in seq]
count = 0
switches = 0
current_seq = seq
current_seq_state = True
state = seq_rev[0]
for i in range(len(seq)):
	if current_seq[i] != state:
		count += 1
	elif switches < 2:
		switches += 1
		if current_seq_state:
			current_seq = seq_rev
		else:
			current_seq = seq
		current_seq_state = not current_seq_state
		count += 1
	state = current_seq[i]
print(count)


(n, tab, changes) = (int(input()), str(input()), 1)
for i in range(1, n):
	changes += 1 if tab[i] != tab[i - 1] else 0
print(min(changes + 2, n))


import sys
input = sys.stdin.readline
t = 1
while t:
	t -= 1
	n = int(input())
	s = input()
	res = 1
	for i in range(1, n):
		res += 1 if s[i] != s[i - 1] else 0
	print(min(n, res + 2))


n = int(input())
t = [int(i) for i in input()]
ch = 0
sm = 0
for i in range(n - 1):
	if t[i] == t[i + 1]:
		sm += 1
	else:
		ch += 1
print(ch + min(sm, 2) + 1)


n = int(input())
seq = input()
prev = -1
ans = 0
for e in seq:
	if e != prev:
		ans += 1
	prev = e
print(min(n, ans + 2))


n = int(input())
s = input()
(cur, arr) = (1, [])
for i in range(1, n):
	if s[i] == s[i - 1]:
		cur += 1
	else:
		arr.append(cur)
		cur = 1
arr.append(cur)
cur = 0
ans = len(arr)
for i in arr:
	if i > 2:
		exit(print(ans + 2))
	if i == 2:
		cur += 1
print(ans + min(2, cur))


N = int(input())
s = input()
count1 = []
x = s[0]
i = 1
count = 1
while i < N:
	if s[i] == s[i - 1]:
		count += 1
	else:
		count1.append(count)
		count = 1
	i += 1
count1.append(count)
if any((i > 2 for i in count1)):
	print(len(count1) + 2)
elif count1.count(2) > 1:
	print(len(count1) + 2)
elif count1.count(2) == 1:
	print(len(count1) + 1)
else:
	print(len(count1))


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

def si():
	return input()

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

def li():
	return list(mi())
n = ii()
s = si()
if n == 1:
	print(1)
else:
	cnt = 1
	st = s[0]
	for i in range(1, n):
		if s[i] != st:
			cnt += 1
			st = s[i]
	print(min(cnt + 2, n))


__author__ = 'MoonBall'
import sys
T = 1

def process():
	input()
	s = input()
	if len(s) == 1:
		print(1)
		return
	b = []
	for x in s:
		if not b or b[-1][0] != x:
			b.append((x, 1))
		else:
			b[-1] = (b[-1][0], b[-1][1] + 1)
	ans = len(b)
	c2 = 0
	c3 = 0
	for x in b:
		if x[1] >= 2:
			c2 = c2 + 1
			ans = max(ans, len(b) + 1)
		if x[1] >= 3:
			c3 = c3 + 1
	if c2 >= 2:
		ans = max(ans, len(b) + 2)
	if c3 >= 1:
		ans = max(ans, len(b) + 2)
	print(ans)
for _ in range(T):
	process()


n = int(input())
s = input()
cnt = 1
last = s[0]
for i in range(1, len(s)):
	if s[i] != last:
		cnt += 1
		last = s[i]
if s.count('111') or s.count('000') or s.count('00') + s.count('11') > 1:
	print(cnt + 2)
elif s.count('11') + s.count('00'):
	print(cnt + 1)
else:
	print(cnt)


n = int(input())
s = input()
cnt = 0
for i in range(len(s) - 1):
	if s[i] == s[i + 1]:
		cnt += 1
cnt -= 2
cnt = max(0, cnt)
print(n - cnt)


n = int(input())
s = input()
c = 1
seg = []
for i in range(1, n):
	if s[i] == s[i - 1]:
		c += 1
	else:
		seg.append(c)
		c = 1
seg.append(c)
f = 0
for i in range(len(seg)):
	if seg[i] >= 3:
		f = max(f, 2)
if seg[0] == 1 and seg[len(seg) - 1] == 2 or (seg[0] == 2 and seg[len(seg) - 1] == 1):
	f = max(1, f)
if seg[0] == seg[len(seg) - 1] == 2:
	f = max(f, 2)
print(min(n, len(seg) + 2))