Kolya got string s for his birthday, the string consists of small English letters. He immediately added k more characters to the right of the string.

Then Borya came and said that the new string contained a tandem repeat of length l as a substring. How large could l be?

See notes for definition of a tandem repeat.


-----Input-----

The first line contains s (1 ≤ |s| ≤ 200). This string contains only small English letters. The second line contains number k (1 ≤ k ≤ 200) — the number of the added characters.


-----Output-----

Print a single number — the maximum length of the tandem repeat that could have occurred in the new string.


-----Examples-----
Input
aaba
2

Output
6

Input
aaabbbb
2

Output
6

Input
abracadabra
10

Output
20



-----Note-----

A tandem repeat of length 2n is string s, where for any position i (1 ≤ i ≤ n) the following condition fulfills: s_{i} = s_{i} + n.

In the first sample Kolya could obtain a string aabaab, in the second — aaabbbbbb, in the third — abracadabrabracadabra.

Difficulty: interview

Starter code:

Solutions:
3

import sys

s = sys.stdin.readline().strip()
k = int(sys.stdin.readline())
s += '*' * k

def is_tandem(s):
    # print(s)
    n = len(s) // 2
    a, b = s[:n], s[n:]
    for i in range(n):
        if a[i] == '*' or b[i] == '*': continue
        if a[i] != b[i]:
            return False
    return True

l = 0
for i in range(len(s)):  # Beginning of tandem
    for n in range(2, len(s) - i + 1, 2):  # Length of tandem
        if is_tandem(s[i:i+n]):
            l = max(l, n)
print(l)


s = input()
k = int(input())
ans = 0

def get_max_tandem_repeat(s, n):
    while n > 0:
        for i in range(len(s) - 2):
            if i + 2 * n > len(s):
                n -= 1
                break
            flag = True
            for j in range(i, i + n):
                if s[j] != s[j+n] and s[j+n] != '_':
                    flag = False
                    break
            if flag:
                return n * 2

if k >= len(s):
    ans = (k + len(s)) // 2 * 2
else:
    s = s + '_' * k
    n = len(s) // 2
    ans = get_max_tandem_repeat(s, n)

print(ans)


s = input()
k = int(input())
le = len(s) + k
m = 0
for i in range(len(s)):
    j = 1
    while i+2*j <= le:
        mi = i + j
        la = i + 2*j
        if mi >= len(s):
            m = max(m, j)
        if la <= len(s) and s[i:mi] == s[mi:la]:
            m = max(m, j)
        if mi < len(s):
            xl = len(s) - mi
            if s[i:i + xl] == s[mi:len(s)]:
                m = max(m, j)
        j += 1
print(2*m)


s = input().rstrip()
k = int(input())
if k > len(s):
    print((len(s) + k) - ((len(s) + k) % 2 == 1))
else:
    aux = []
    
    for j in range(1, len(s)):
        i = len(s) - 1
        cnt = 0
        while i - j >= 0 and s[i] == s[i - j]:
            i -= 1
            cnt += 1
            if cnt == j:
                break
        diff = i - (len(s) - j - 1)
        if diff <= k:
            aux.append(2 * j)
    aux.append(2 * k)
    
    for i in range(len(s)):
        for j in range((len(s) - i) // 2):
            if s[i:i + j] == s[i + j:i + 2 * j]:
                aux.append(2 * j)
                
    print(max(aux))


s = input()
k = int(input())
s = s + '?'*k
for i in range(len(s)//2 + 1):
    a=[0]*len(s)
    for j in range(len(s)-i):
        if (s[j] == s[j+i])or (s[j+i] == '?'):
            a[j] = 1
    c = 0
    mx = 0
    for j in a:
        if j == 1:
            c+=1
        else:
            mx = max(mx,c)
            c = 0
    if mx >= i:
        ans = i*2
print(ans)

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

import sys

s = input()
k, = readln()
s += '?' * k

ans = (len(s) // 2) * 2
while ans:
    for i in range(len(s) - ans + 1):
        flag = True
        for j in range(i, i + ans // 2):
            #print(ans, i, j, flag)
            flag = flag and (s[j] == s[j + ans // 2] or s[j + ans // 2] == '?')
        if flag:
            print(ans)
            return
    ans -= 2

t, k = input(), int(input())
n = len(t)
s = min(k, (n + k) // 2)
for i in range(n - k):
    for j in range(i + s + 1, min(n, (n + i + k) // 2 + 1)):
        d = j - i
        if n - j > d:
            if t[i: j] == t[j: j + d]: s = d
        elif t[i: n - d] == t[j: n]: s = d
print(2 * s)

s=input()
k=int(input())

s+='?'*k
n=len(s)
best=0
for i in range(n):
    for j in range(i+1,n):
        if((j-i+1)%2!=0):
            continue
        x=j-i+1
        valid=True
        for e in range(i,j+1):
            if(e+x//2>j):
                break
            if(s[e]=='?' or s[e+x//2]=='?'  or s[e]==s[e+x//2]):
                continue
            valid=False
        if(valid):
            best=max(best,x)
print(best)


t, k = input(), int(input())
n = len(t)
s = min(k, (n + k) // 2)
for i in range(n - k):
    for j in range(i + s + 1, min(n, (n + i + k) // 2 + 1)):
        d = j - i
        if n - j > d:
            if t[i: j] == t[j: j + d]: s = d
        elif t[i: n - d] == t[j: n]: s = d
print(2 * s)

def tandemRepeat(i,j):
    a=s[i:i+j-1]
    b=s[i-j:i-1]
    for k in range(len(a)):
        if a[k]==b[k] or a[k]=='*' or b[k]=='*':
            continue
        else:
            return False
    return True

s=input()
n=int(input())
s=s+("*"*n)
#print(s)
ans=-1
for i in range(len(s)):
    for j in range(1,len(s)):
        if i+j-1<len(s) and i-j>=0 and tandemRepeat(i,j):
            if ans<j : ans=j
print(ans*2)
            


t, k = input(), int(input())
n = len(t)
s = min(k, (n + k) // 2)
for i in range(n - k):
    for j in range(i + s + 1, min(n, (n + i + k) // 2 + 1)):
        d = j - i
        if n - j > d:
            if t[i: j] == t[j: j + d]: s = d
        elif t[i: n - d] == t[j: n]: s = d
print(2 * s)

s, r = input(), int(input())


def compare(a, b):
    return a[:len(b)] == b

def f(s, n, N):
    if not s or n < 2*N:
        return N
    for i in range(n//2, 0, -1):
        #print(s, n, i, N)
        if compare(s[:i], s[i:2 * i]):
            return f(s[1:], n-1, max(i, N))
    return f(s[1:], n-1, N)
if len(s) < r:
    print((len(s) + r) // 2 * 2)
else:
    print(2*f(s, len(s) + r, 0))

st=input()
num=int(input())
maxlen=0
for start in range(len(st)+num):
  for end in range(start+1,len(st)+num,2):
    middle=(end+start+1)//2
    ans=True
    for it in range(min(len(st)-middle,end-middle)):
      if(st[start+it]!=st[middle+it]):
        ans=False
        break
    if ans:
      maxlen=max(maxlen,end-start+1)
print(maxlen)


a=input()
b=int(input())
j=0
l=0
for start in range(len(a)+b):
    for end in range(start+1,len(a)+b):
        if ((end-start)+1)%2==0:
            middle=(start+end)//2+1
            k=0
            for traverse in range(start,len(a)):
                if k+middle>=len(a) or k+middle>end:
                    j=end-start+1
                    if j>l:
                        l=j
                elif k+middle<len(a) and a[traverse]!=a[middle+k]:
                    break
                elif k+middle<len(a) and a[traverse]==a[middle+k]:
                    k+=1
print(l)
                        



s = input()
n = len(s)
k = int(input())
best = 0
if k >= n:
    best = (k + n) // 2 * 2
for st in range(n):
    for ln in range(2, n - st):
        if s[st:st+ln//2] == s[st+ln//2:st+ln]:
            best = max(best, ln)
    
for st1 in range(n):
    if (n + k - st1) % 2 == 0:
        lens = (n + k - st1) // 2
        nlen = lens - k
        st2 = st1 + lens
        if s[st1:(st1+nlen)] == s[st2:]:
            best = max(best, lens*2)
print(best)    

def tandem(n, a, i):
    for k in range(i, i + n):
        if a[k] != a[k + n] and a[k + n] != '??':
            return 0
    return 1
 
s = list(input().strip())
k = int(input())
s += ['??' for i in range(k)]

res = 0

for i in range(len(s)):
    for n in range(1, (len(s) - i) // 2 + 1):
        if tandem(n, s, i):
            res = max(res, n * 2)
print(res)

def main():
    s = input()
    k = int(input())
    
    s += '?' * k
    
    N = len(s)
    
    result = 0
    
    for l in range(1, N):
        count = 0
        for i in range(N - l):
            if s[i] == s[i + l] or s[i + l] == '?':
                count += 1
                if count == l:
                    result = l
                    break
            else:
                count = 0
    
    print(result * 2)
                    

main()


def match(str1, str2):
    for t in range(len(str1)):
        if str1[t]!=str2[t] and str2[t]!='_':
            return False
    return True

string=input()
k=int(input())

length=len(string)
mark = False
if k>=length:
    print(2*int((length+k)/2))
else:
    s=string+k*'_'
    n=int(len(s)/2)
    for i in range(n, 0, -1):
        for j in range(len(s)-2*i+1):
            if match(s[j:i+j], s[i+j:i+i+j]) and mark == False:
                print(2*i)
                mark = True

#input

s=str(input())
k=int(input())



#variables
a=0
def tandem(string):
	if len(string)%2==1:
		return False
	else:
		if string[:len(string)//2]==string[len(string)//2:]:
			return True
		else:
			return False


#main
if len(s)<=k:
	a=2*((len(s)+k)//2)
else:
	a=2*k

for i in range(0,len(s)-1):
	for j in range(i+1,len(s)):
		if tandem(s[i:j+1]):
			a=max(a,j-i+1)

for i in range(len(s)-1):
	if s[i]==s[-1]:
		x=0
		while i-x>=0:
			if s[i-x]==s[-1-x] and i+x<len(s):
				x+=1
			else:
				break
		if len(s)-i-x-1<=k:
			a=max(a,2*(len(s)-i-1))

print(a)

import sys
#fin=open('F:/OJ/OJ/in.txt','r')
#sys.stdin=fin

str=input()
k=int(input())
ans=0
if(k>=len(str)):
    print((k+len(str))//2*2)
    return
for i in range(len(str)):
    for j in range(0,i+1):
        len1=len(str[j:i+1])
        len2=len(str[i+1:])
        minn=min(len1,len2)
        #print( i,j)
        #print(len1,len2)
        if(str[j:j+minn]==str[i+1:i+1+minn]):
            if(minn==len1):
                ans=max(ans,len1*2)
            elif(k+len2>=len1):
                ans=max(ans,len1*2)
                
print(ans)


s=input()
k=int(input())
n=len(s)

if k>=n:
    print(int(2*((n+k)//2)))
    raise SystemExit
ll=0
for i in range(k+1):
  for l in range((n+i)//2,i-1,-1):
    if s[n-(l-i):n]==s[n+i-2*l:n-l]:
        if l>ll:
            ll=l
        break

j=ll
while 2*j<=n:
    j=j+1
    for i in range(n-2*j):
        if s[i:i+j]==s[i+j:i+2*j]:
            ll=j
            break
print(int(2*ll))


s = input()
k = int(input())
n = len(s)
ans = min(2 * k, 2 * n)
start = min(k + 1, n + 1)
end = (n + k) // 2 + 1
for i in range(start, end):
    flag = True
    for j in range(n - 1, max(-1, n - (i - k) - 1), -1):
        if s[j] != s[j - i]:
            flag = False
            break
    if flag:
        ans = 2 * i
for l in range(n):
    for d in range(n - l):
        if l + 2 * d <= n and s[l:l + d] == s[l + d:l + 2 * d]:
            ans = max(ans, d * 2)
print(ans)


s = input()
k = int(input())
m = len(s) + k
ans = 0
if k >= len(s):
  ans = m - m % 2
for x in range(len(s)//2+1, 0, -1):
  for y in range(len(s)-2*x):
    if s[y:y+x] == s[y+x:y+2*x]:
      ans = max(ans, 2*x)
      # print(s[y:y+x], s[y+x:y+2*x])
for l in range(m//2, 0, -1):
  c = s[m-2*l:m-l]
  if c[:l-k] == s[m-l:]:
    ans = max(ans, 2*l)
    break
print(ans)