The only difference between easy and hard versions is the length of the string.

You are given a string $s$ and a string $t$, both consisting only of lowercase Latin letters. It is guaranteed that $t$ can be obtained from $s$ by removing some (possibly, zero) number of characters (not necessary contiguous) from $s$ without changing order of remaining characters (in other words, it is guaranteed that $t$ is a subsequence of $s$).

For example, the strings "test", "tst", "tt", "et" and "" are subsequences of the string "test". But the strings "tset", "se", "contest" are not subsequences of the string "test".

You want to remove some substring (contiguous subsequence) from $s$ of maximum possible length such that after removing this substring $t$ will remain a subsequence of $s$.

If you want to remove the substring $s[l;r]$ then the string $s$ will be transformed to $s_1 s_2 \dots s_{l-1} s_{r+1} s_{r+2} \dots s_{|s|-1} s_{|s|}$ (where $|s|$ is the length of $s$).

Your task is to find the maximum possible length of the substring you can remove so that $t$ is still a subsequence of $s$.


-----Input-----

The first line of the input contains one string $s$ consisting of at least $1$ and at most $200$ lowercase Latin letters.

The second line of the input contains one string $t$ consisting of at least $1$ and at most $200$ lowercase Latin letters.

It is guaranteed that $t$ is a subsequence of $s$.


-----Output-----

Print one integer — the maximum possible length of the substring you can remove so that $t$ is still a subsequence of $s$.


-----Examples-----
Input
bbaba
bb

Output
3

Input
baaba
ab

Output
2

Input
abcde
abcde

Output
0

Input
asdfasdf
fasd

Output
3

Difficulty: introductory

Starter code:

Solutions:
s = input()
t = input()
l, r = [0]*len(t), [0]*len(t)
li, ri = 0, len(s) - 1
for i in range(len(t)):
    while s[ li ] != t[ i ]:
        li += 1
    while s[ ri ] != t[ - i - 1 ]:
        ri -= 1
    l[ i ] = li
    r[ -i -1 ] = ri
    li += 1
    ri -= 1

print( max( [ r[ 0 ], len(s) - l[ -1 ] - 1 ] + [ max( 0, r[ i ] - l[ i - 1 ] ) - 1 for i in range( 1, len(t) ) ] ) )


def check(mid):
    qa = False
    for i in range(n - mid + 1):
        u = 0
        for j in range(i):
            if u < m and s[j] == t[u]:
                u += 1
        for j in range(i + mid, n):
            if u < m and s[j] == t[u]:
                u += 1
        if u == m:
            qa = True
            break
    return qa


s = input()
t = input()
n = len(s)
m = len(t)
l = -1
r = n - m + 1
while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)

def check(s, t):
	i = 0
	j = 0
	while i < len(s) and j < len(t):
		if (s[i] == t[j]):
			j += 1
		i += 1
	return j == len(t)
s = input()
t = input()
ans = 0
for i in range(len(s) + 1):
	for j in range(i, len(s) + 1):
		if (check(s[:i] + s[j:], t)):
			ans = max(ans, j - i)
print(ans)


s = input()
t = input()

forward = []

backward = []

rptr = 0

for i in range(len(s)):
    if rptr == len(t):
        break
    if s[i] == t[rptr]:
        forward.append(i)
        rptr += 1

rptr = len(t)-1
for i in range(len(s)-1, -1, -1):
    if rptr == -1:
        break
    if s[i] == t[rptr]:
        backward.append(i)
        rptr -= 1

backward = backward[::-1]
backward.append(forward[-1])

mx = max(forward[0], len(s)-1-backward[-2], len(s)-1-forward[-1], backward[0])
#print(mx)
for i in range(len(t)):
    mx = max(mx, abs(forward[i] - backward[i+1])-1)
    #print(i, mx)
print(mx)


s=str(input())
t=str(input())
i=0
j=0
arr1=[]
while(i<len(s)):
	if(s[i]==t[j]):
		arr1.append(i+1)
		j+=1
	i+=1
	if(j==len(t)):
		break

i=len(s)-1
j=len(t)-1
arr2=[0]*len(t)
while(i>=0):
	if(s[i]==t[j]):
		arr2[j]=i+1
		j-=1
	i-=1
	if(j==-1):
		break

ans=max(arr2[0]-1,len(s)-arr1[-1])

for i in range(len(t)-1):
	ans=max(ans,arr2[i+1]-arr1[i]-1)

print(ans)



from sys import stdin
s=stdin.readline().strip()
s1=stdin.readline().strip()
dp=[-1 for i in range(len(s1)+1)]
dp1=[-1 for i in range(len(s1)+1)]
x=0
for i in range(len(s)):
    if s[i]==s1[x]:
        dp[x+1]=i
        x+=1
        if x>=len(s1):
            break
x=len(s1)-1
y=1
dp[0]=-1
dp1[0]=len(s)
for i in range(len(s)-1,-1,-1):
    if s[i]==s1[x]:
        dp1[y]=i
        x-=1
        y+=1
        if x<0:
            break

ans=0
for i in range(len(s1)+1):
    ans=max(dp1[len(s1)-i]-dp[i]-1,ans)
    ans=max(dp[len(s1)-i]-dp1[i]-1,ans)
    
        
print(ans)


def remove(s,t,start,end):
    arr = []
    for i in range(start):
        arr.append(s[i])

    for i in range(end+1,len(s)):
        arr.append(s[i])


    i = 0
    j = 0
    while i < len(arr) and j < len(t):
        if arr[i] == t[j]:
            i += 1
            j += 1
        else:
            i += 1

    if j == len(t):
        return True

    return False

def solve(s,t):
    n = len(s)
    ans = 0
    for i in range(n):
        for j in range(i,n):
            if remove(s,t,i,j):
                ans = max(ans,j-i+1)

    print(ans)

def main():
    s = input()
    t = input()
    solve(s,t)


main()


s = input()
t = input()
n = len(s)

ans = 0
for i in range(n):
    for j in range(i, n):
        st = s[ : i] + s[j+1 :]
        #print(st)
        
        cur, ok = 0, 0
        
        for ch in st:
            if ch == t[cur]:
                cur += 1
            if cur == len(t):
                ok = 1
                break
            
        if ok == 1:
            ans = max(ans, len(s) - len(st))
print(ans)



def main():

    s = input()
    t = input()
    n = len(s)

    ans = 0
    for i in range(n):
        for j in range(i, n):
            a = s[ : i] 
            b = s[j+1 :]
            st = a+b
            cur, ok = 0, 0
            
            for ch in st:
                if ch == t[cur]:
                    cur += 1
                if cur == len(t):
                    ok = 1
                    break
                
            if ok == 1:
                ans = max(ans, len(s) - len(st))
    return ans

print(main())


from sys import stdin
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: list(map(int, rd().strip().split()))

s = str(rd().strip())

t = str(rd().strip())
s = '0' + s

canl = [0] * (len(s) + 10)
canr = [0] * (len(s) + 10)

j = 0
for i,v in enumerate(s):

    if j<len(t) and v == t[j]:
        j += 1
    canl[i] = j

j = len(t) - 1

for i in range(len(s)-1,-1,-1):
    if j>=0 and s[i] == t[j]:
        j -= 1
    canr[i] = len(t)-j-1


def check(x):
    if x > len(s):
        return False

    for i in range(1,len(s) - x+1):
        l = i - 1
        r = i + x

        if canl[l] + canr[r] >= len(t):

            return True

    return False


l = 0
r = len(s)


while l<r:
    mid = (l+r)//2
    if check(mid):
        l = mid + 1
    else:
        r = mid


print(r-1)







s = input()
t = input()
n = len(s)
m = len(t)
l = [-1]
r = [n]
c = 0
for i in range(n):
    if s[i] == t[c]:
        l.append(i)
        c += 1
        if c >= m:
            break
c = 0
for i in range(n):
    if s[-1-i] == t[-1-c]:
        r.append(n-1-i)
        c += 1
        if c >= m:
            break
mx = 0
for i in range(m+1):
    mx = max(mx, r[m-i]-l[i]-1)
print(mx)


def subseq(a, b):
    j = 0
    for i in range(len(a)):
        if j < len(b) and a[i] == b[j]:
            j = j + 1
    if j == len(b):
        return True
    else:
        return False


s = input()
t = input()
ans = 0

for i in range(len(s)):
    for j in range(i, len(s)):
        cur = s[:i] + s[j+1:len(s)]
        if subseq(cur, t) and j - i + 1 > ans:
            ans = j - i + 1
print (ans)


s = input()
t = input()


def compute_prefix(s, t):
    prefix = [0 for i in range(len(t) + 1)]
    i = 0
    j = 0
    while i < len(t):
        while s[j] != t[i]:
            j += 1
        prefix[i+1] = j+1
        i += 1
        j += 1
    return prefix


prefix = compute_prefix(s, t)
suffix = compute_prefix(s[::-1], t[::-1])
res = 0
for i in range(len(t) + 1):
    res = max(res, len(s) - (prefix[i] + suffix[len(t) - i]))
print(res)


def pp(s, t):
    last = 0
    for i in t:
        if last == len(s):
            return 0
        while(s[last] != i):
            last += 1
            if last == len(s):
                return 0
        last += 1
    return 1

s, t = input(), input()
ans = 0
n = len(s)
for i in range(n):
    for j in range(i, n):
        if pp(s[:i] + s[(j + 1):], t):
            ans = max(ans, j - i + 1)
print(ans)


# print(pp('bbaba', 'bb'))

# s = '0123456789'
# print(s[:2] + s[4:])


S = input()
T = input()
N, M = len(S), len(T)

def calc(s, t):
    X = [0] * len(s)
    j = 0
    for i in range(len(s)):
        if j >= len(t):
            X[i] = j
        elif s[i] == t[j]:
            X[i] = j+1
            j += 1
        else:
            X[i] = X[i-1]
    return [0] + X

        
A, B = calc(S, T), calc(S[::-1], T[::-1])[::-1]
# print(A, B)
l, r = 0, N
while r-l>1:
    m = (l+r)//2
    C = [A[i]+B[i+m] for i in range(N-m+1)]
    # print("m, C =", m, C)
    if max(C) >= M:
        l = m
    else:
        r = m
print(l)


s = input()
t = input()

i = 0
l = []
for c in t:
    while s[i] != c:
        i += 1
    l.append(i)
    i += 1

i = len(s)-1
r = []
for c in t[::-1]:
    while s[i] != c:
        i -= 1
    r.append(i)
    i -= 1

r.reverse()

mx = r[0]
for i in range(len(t)-1):
    mx = max(mx, r[i+1] - l[i] - 1)
mx = max(mx, len(s)-l[-1]-1)

print(mx)

# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
from sys import stdin, stdout
import math
from math import gcd,sqrt

def isSubSequence(str1,str2,m,n): 
      
    j = 0    # Index of str1 
    i = 0    # Index of str2 
      
    # Traverse both str1 and str2 
    # Compare current character of str2 with  
    # first unmatched character of str1 
    # If matched, then move ahead in str1 
      
    while j<m and i<n: 
        if str1[j] == str2[i]:     
            j = j+1    
        i = i + 1
          
    # If all characters of str1 matched, then j is equal to m 
    return j==m

#T = int(input())
#N = int(input())
s1 = input()
N = len(s1)
s2 = input()
#N,M,Q = [int(x) for x in stdin.readline().split()]
#arr = [int(x) for x in stdin.readline().split()]

res = 0
for i in range(N):
    for j in range(i,N):
        s = s1[:i] + s1[(j+1):]
        # check subsequence
        #print(s)
        if isSubSequence(s2,s,len(s2),len(s)):
            res = max(res,j-i+1)
            
print(res)


s = input()
t = input()

pos = [[-1, -1] for i in range(len(t))]

ptr = 0
for i,c in enumerate(t):
    while s[ptr] != c:
        ptr += 1
    pos[i][0] = ptr
    ptr += 1

ptr = len(s) - 1
for i in range(len(t)-1, -1, -1):
    c = t[i]
    while s[ptr] != c:
        ptr -= 1
    pos[i][1] = ptr
    ptr -= 1

best = max(pos[0][1], len(s)-pos[-1][0]-1)
for i in range(1, len(pos)):
    best = max(best, pos[i][1] - pos[i-1][0] - 1)

print(best)


def is_subseq(s, t):
	if(len(t) > len(s)):
		return False
	i = 0
	j = 0
	# is t a subsequence of s?
	while(j < len(t)):
		if(s[i]==t[j]):
			i += 1
			j += 1
		else:
			i += 1
		if(i==len(s)):
			break
	return j==len(t)
s = input()
t = input()
mx = 0
for i in range(len(s)):
	for j in range(len(s)):
		l = min(i, j)
		r = max(i, j)
		s2 = s[:l]+s[r:]
		if(is_subseq(s2, t)==True):
			mx = max(mx, r-l)
			# print(s2)
for i in range(len(s)):
	s2 = s[:i]
	if(is_subseq(s2, t)==True):
		mx = max(mx, len(s)-i)
	s2 = s[i:]
	if(is_subseq(s2, t)==True):
		mx = max(mx, i)

print(mx)

s = input()
t = input()
fp = [-1]
tp = 0
for i in range(len(s)):
    if s[i] == t[tp]:
        fp.append(i)
        tp += 1
        if tp == len(t):
            break
lp = [len(s)]
tp = len(t) - 1
for i in range(len(s) -1, -1 , -1):
    if s[i] == t[tp]:
        lp.append(i)
        tp -= 1
        if tp == -1:
            break
lp.reverse()
print(max([ (l-f) for (l,f) in zip(lp, fp)]) - 1)

s = input()
t = input()
n = len(s)
m = len(t)
le = []
ri = []
ans = 0
p = 0
for i in range(n):
    if p < m:
        if s[i] == t[p]:
            le.append(i)
            if p == m - 1:
                ans = max(ans, n - 1 - i)
            p += 1
p = m - 1
for j in range(n - 1, -1, -1):
    if p >= 0:
        if s[j] == t[p]:
            ri.append(j)
            if p == 0:
                ans = max(ans, j - 0)
            p -= 1
ri.reverse()
for k in range(m - 1):
    ans = max(ans, ri[k + 1] - le[k] - 1)
print(ans)

import io, os
#input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline

def check(d):
	for i in range(len(s) - d + 1):
		pos = 0
		#print(s[:i] + s[i + d:], i)
		for x in s[:i]:
			if x == s1[pos]:
				pos += 1
				if pos == len(s1):
					return True
		for x in s[i + d:]:
			if x == s1[pos]:
				pos += 1
				if pos == len(s1):
					return True
	return False

s = input()
s1 = input()

l = 0
r = len(s)

while r - l > 1:
	mid = (r + l) // 2
	if check(mid):
		l = mid
	else:
		r = mid

print(l)
"""
check(3)
"""


from sys import stdin
input = stdin.readline

s = input()
t = input()

n = len(t)
low = [0 for i in range(len(t))]
high = [0 for i in range(len(t))]

acc = 0

for i in range(n):
    acc_t = t[i]
    
    while acc_t != s[acc]: acc += 1
    low[i] = acc
    acc += 1

acc = len(s)-1
    
for i in range(len(t)):
    acc_t = t[n-i-1]
    
    while acc_t != s[acc]: acc -= 1
    high[n-i-1] = acc
    acc -= 1
    
res = max(high[0], len(s)-low[n-1]-1)

for i in range(n-1):
    res = max(res, high[i+1]-low[i]-1)
    
print(res)

from sys import stdin, stdout

input = stdin.readline

s, t = list(map(str, stdin.read().split()))

n, m = len(s), len(t)
a = [0] * m
b = [0] * m

pos = 0
for i in range(n):
    if s[i] == t[pos]:
        a[pos] = i
        pos += 1
        if pos == m:
            break

pos = m - 1
for i in range(n - 1, -1, -1):
    if s[i] == t[pos]:
        b[pos] = i
        pos -= 1
        if pos == -1:
            break

res = max(b[0], n - (a[-1] + 1))
for i in range(m - 1):
    res = max(res, (b[i + 1] - 1) - (a[i] + 1) + 1)

print(res)


def isSubSequence(str1,str2,m,n): 
    j = 0 
    i = 0 
    while j<m and i<n: 
        if str1[j] == str2[i]:     
            j = j+1    
        i = i + 1
    return j==m
s=input()
t=input()
LengthT=len(t)
A=[]
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        p=s[:i]+s[j:]
        if isSubSequence(t,p,LengthT,len(p)):
            A.append(j-i)
try:
    print(max(A))
except:
    print(0)