You are given a string s consisting of n lowercase Latin letters. You have to type this string using your keyboard.

Initially, you have an empty string. Until you type the whole string, you may perform the following operation:  add a character to the end of the string. 

Besides, at most once you may perform one additional operation: copy the string and append it to itself.

For example, if you have to type string abcabca, you can type it in 7 operations if you type all the characters one by one. However, you can type it in 5 operations if you type the string abc first and then copy it and type the last character.

If you have to type string aaaaaaaaa, the best option is to type 4 characters one by one, then copy the string, and then type the remaining character.

Print the minimum number of operations you need to type the given string.


-----Input-----

The first line of the input containing only one integer number n (1 ≤ n ≤ 100) — the length of the string you have to type. The second line containing the string s consisting of n lowercase Latin letters.


-----Output-----

Print one integer number — the minimum number of operations you need to type the given string.


-----Examples-----
Input
7
abcabca

Output
5

Input
8
abcdefgh

Output
8



-----Note-----

The first test described in the problem statement.

In the second test you can only type all the characters one by one.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
st = input()
ans = n
now = ''
ma = 0
for i in range(n // 2):
    now += st[i]
    t = ''
    for j in range(i + 1, 2 * i + 2):
        t += st[j]
    if t == now:
        ma = i
print(ans - ma)


n = int(input())
strng = input().strip()
res = len(strng)
st = len(strng)//2
while st>0:
    if strng[:st] == strng[st:st*2]:
        print(res - st +1)
        return
    st -= 1

print(res)





import getpass
import sys
import math
import random
import itertools
import bisect
import time

files = True
debug = False

if getpass.getuser() == 'frohenk' and files:
    debug = True
    sys.stdin = open("test.in")
    # sys.stdout = open('test.out', 'w')
elif files:
    # fname = "gift"
    # sys.stdin = open("%s.in" % fname)
    # sys.stdout = open('%s.out' % fname, 'w')
    pass


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


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


def range_sum(a, b):
    ass = (((b - a + 1) // 2) * (a + b))
    if (a - b) % 2 == 0:
        ass += (b - a + 2) // 2
    return ass


def comba(n, x):
    return (math.factorial(n) // math.factorial(n - x)) // math.factorial(x)


n = ria()[0]
suma = n
st = input()
mx = 0
for i in range(1, n + 1):
    if i + i <= n:
        if st[:i] == st[i:i + i]:
            mx = max(mx, len(st[:i]) - 1)
print(n - mx)


input()
s=input()
ans=len(s)
for i in range(len(s)//2,0,-1):
	if s[:i]==s[i:2*i]:
		ans=len(s)-i+1
		break
print(ans)

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

anw = n

def calc(pos):
  x = s[:pos] + s[:pos]
  if x == s[:pos*2]:
    return 1+n-pos
  return 1e9

for i in range(n):
  anw = min(anw, calc(i))
  
print(anw)

n = int(input())
s = input()
ans = n
for i in range(n):
    ss = s[:i]
    if 2*i <= n and s[:i] == s[i:2*i]:
        ans = min(ans, n - i +1)
print(ans)

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

ans = n
for i in range(n // 2 + 1):
    if s[:i] == s[i:2 * i]:
        # print (s[:i])
        ans = min(ans, i + 1 + n - 2 * i)
print(ans)


R = lambda : list(map(int, input().split()))
n = int(input())
s = input()

for i in reversed(list(range(n//2))):
    if s[0:i+1]==s[i+1:2*i+2]:
        print((n-i)); return;

print(n)


def test(k):
    if len(s) >= 2 * k:
        return s[:k] == s[k: 2 * k]
    return False


n = int(input())
s = input()
d = 0
for i in range(len(s) + 1):
    if test(i):
        d = i
print(min(len(s), len(s) - 2 * d + d + 1))


n=int(input())
s=input()
imp=0
for i in range(n//2,0,-1):
    if(s[:i]==s[i:2*i]):
        imp=i
        break
print(min(n,n-imp+1))

n = int(input())
s = input()
currents = s
ans = 0
while (len(currents)>0):
    if (len(currents)%2==0) and (currents[0:len(currents)//2]==currents[len(currents)//2:len(s)]):
            ans = ans+len(currents)//2
            ans+=1
            break
    else:
        currents = currents[0:len(currents)-1]
        ans = ans+1
print(ans)            
    
        
    

    


n = int(input())
a = input()
o = ''
m = 0
for i in range(n//2):
    #print(a[:i+1],a[i+1:i+i+2])
    if a[:i+1] == a[i+1:i+i+2]:
     #   print(a[:i+1])
        m = i
print(n-m)


N = int(input())
S = input()
copied = 1
for i in range(1,N//2+1):
    # print(i, "\"{}\"".format(S[:i]), "\"{}\"".format(S[i:2*i]))
    if S[:i] == S[i:2*i]:
        copied = i
print(N-copied+1)


n = int(input())
s = input()
ans = 1e18
for c in range(n // 2 + 1):
    curr = c + 1 + (n - 2 * c)
    if c == 0:
        curr -= 1
    s1 = s[:c] * 2
    b = True
    for i in range(len(s1)):
        if s1[i] != s[i]:
            b = False
            break
    #print(c, b, curr, s1)
    if b:
        ans = min(ans, curr)
print(ans)

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


n = int(input())

s = input()

ss = ""

i = 0
longest  = 0

for i in range(int(n/2)):
	#print(s[0:i+1])
	#print(s[i+1:i+i+1+1])
	if s[0:i+1] == s[i+1:i+i+1+1]:
		longest = i

ans = n-longest

print(ans)


l = int(input())
k = input()
ans = 0
for i in range(1, (l//2) + 1):
    flag = 1
    for j in range(0, i):
        if k[j] != k[i + j]:
            flag = 0
            break
    if flag == 1:
        ans = max(ans, i)
su = l - (ans)
if ans > 0:
    su += 1
print(su)


n = int(input())
s = str(input())
ans = len(s)
for i in range(1, n+1):
    if s[:i] + s[:i] == s[:2*i] and 2*i <= n:
        ans = min(ans, n-i+1)
print(ans)


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

cnt = 0
for i in range(2,n//2+1):
	if s[:i] == s[i:i+i]:
		cnt = i

if cnt == 0:
	print(n)
else:
	print(n - (cnt - 1))



n = int(input())
s = input()
c = 0

for i in range(1, 1 + len(s) // 2):
    if s[:i] == s[i:2 * i]:
        c = i

if c != 0:
    print(n - c + 1)

else:
    print(n)


n = int(input())
seq = input()
count = n
for i in range(1,n//2+1):
    if seq[0:i] == seq[i:min(2*i,n)]:
        count = n + 1 - i
print(count)

n=input()
s=input()
best = 0
for i in range(len(s)//2+1):
	t = s[:i]*2
	# print(t)
	try:
		if s.index(t) == 0:
			best = i
	except:
		pass
if best > 0:
	print(len(s) - best + 1)
else:
	print(len(s))	 

n=int(input())
s=input()
i=0
d=""
ls=[]
mx=-1
while i<n:
    temp=s[0:i+1]
    for j in range(i+1,n+1):
        if temp==s[i+1:j]:
            mx=max(mx,len(temp))
    i+=1
if mx>0:
    print(len(temp)-mx+1)
else:
    print(len(temp))

n = int(input())
s = input()
x = 1
for i in range(1, (n >> 1) + 1):
    if s[:i] == s[i:2 * i]:
        x = i
print(n - x + 1)