Given are two strings S and T.
Let us change some of the characters in S so that T will be a substring of S.
At least how many characters do we need to change?
Here, a substring is a consecutive subsequence. For example, xxx is a substring of yxxxy, but not a substring of xxyxx.

-----Constraints-----
 - The lengths of S and T are each at least 1 and at most 1000.
 - The length of T is at most that of S.
 - S and T consist of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
S
T

-----Output-----
Print the minimum number of characters in S that need to be changed.

-----Sample Input-----
cabacc
abc

-----Sample Output-----
1

For example, changing the fourth character a in S to c will match the second through fourth characters in S to T.
Since S itself does not have T as its substring, this number of changes - one - is the minimum needed.

Difficulty: introductory

Starter code:

Solutions:
s = input()
t = input()
m = 1000
for i in range(len(s) - len(t) + 1):
  c = 0
  for j in range(len(t)):
    if s[i + j] != t[j]:
      c += 1
  m = min(m, c)
print(m)

def resolve(): 
   S = input();T=input()
   count1=[]
   for i in range(len(S)-len(T)+1):
       count2=0
       for j in range(len(T)):
           if S[i:i+len(T)][j]==T[j]:count2+=1
       count1.append(len(T)-count2)

   print(min(count1))
resolve()

S=input()
T=input()

def ans177(S:str, T:str):
    judge_count=0
    ans_count=0
    while judge_count<=len(S)-len(T):
        same_count = 0
        for i in range(len(T)):
            if S[judge_count+i]==T[i]:
                same_count+=1
        if same_count>=ans_count:
            ans_count=same_count
        judge_count+=1
    return len(T)-ans_count

print(ans177(S,T))

s = input()
t = input()
ls = []
for i in range(len(s) - len(t) + 1):
    ls.append(s[i:i+len(t)])
now = 0
minimum = len(t)
for i in range(len(ls)):
    now = 0
    for j in range(len(t)):
        if t[j] == ls[i][j]:
            now += 1
    if len(t) - now < minimum:
        minimum = len(t) - now
print(minimum)


S = input()
T = input()
ans = len(T)

for i in range(len(S)-len(T) + 1):
    ans = min(ans, sum([x[0] != x[1] for x in zip(T,S[i:]) ]))

print(ans)


S=input()
T=input()
t=0
s=0
a=0
while a<=len(S)-len(T):
    u=S[a:a+len(T)]
    for j in range(len(T)):
       if u[j]==T[j]:
          t=t+1
    if s<t:
         s=t
    t=0
    a=a+1
print(len(T)-s)

def b177(s, t):

    ans = 10**8

    for i in range(len(s)-len(t)+1):
        count = 0
        for w in range(len(t)):
            if s[i+w] == t[w]:
                count += 1
        ans = min(ans, len(t)-count)

    return ans

def main():
    s = list(str(input()))
    t = list(str(input()))
    print((b177(s, t)))

def __starting_point():
    main()

__starting_point()

s=input()
t=input()
box=[]
for i in range(len(s)-len(t)+1):
  a=0
  for j in range(len(t)):
    if t[j]!=s[i+j]:
      a+=1
  box.append(a)
print(min(box))

l1 = input()
l2 = input()
n_steps = []

for i in range(len(l1) - len(l2) + 1):
  num = 0
  for i, l in enumerate(l2):
    if l1[i] != l:
      num += 1
  n_steps.append(num) 
  l1 = l1[1:]
n_steps.sort()
print((n_steps[0]))



def answer(s: str, t: str) -> int:
    result = len(t)
    for i in range(len(s) - len(t) + 1):
        count = 0
        for j in range(len(t)):
            if t[j] != s[i + j]:
                count += 1
        result = min(result, count)

    return result


def main():
    s = input()
    t = input()
    print((answer(s, t)))


def __starting_point():
    main()

__starting_point()

s = list(input())
t = list(input())

min = len(t);
for i in range(0, len(s) - len(t) + 1):
  count = 0;
  for j in range(0, len(t)):
    if s[i + j] != t[j]: count += 1
    
  if count < min: min = count
    
print(min)

S = input()
T = input()
count_list = []
count = 0
for i in range(len(S) - len(T) + 1):
    for j in range(len(T)):
        if T[j] == S[j + i]:
            count += 1
    count_list.append(count)
    count = 0
#print(count_list)
ans = len(T) - max(count_list)
print(ans)

import sys
line_long = sys.stdin.readline().strip()
line_sub = sys.stdin.readline().strip()

len_long = len(line_long)
len_sub = len(line_sub)
min_cnt = len_sub
for idx in range(0, len_long - len_sub + 1):
    this_cnt = 0
    for sub_idx in range(0, len_sub):
        if line_sub[sub_idx] != line_long[sub_idx + idx]:
            this_cnt = this_cnt + 1
    min_cnt = min(min_cnt, this_cnt)
print(min_cnt)



S = input()
T = input()


# 解説を読んで解いた
# Sの何文字目から書き換えるか全探索

ans = [0]*(len(S)-len(T)+1)

for i in range(len(S)-len(T)+1):
  st = S[i:i+len(T)]
  # 一致しない文字の数が書き換える回数になる
  for j in range(len(T)):
    if st[j] != T[j]:
      ans[i] += 1 
      #print(ans)

print(min(ans))

s=input()
t=input()
a = len(t)
for i in range(len(s)-len(t)+1):
    a = min(a,sum([x[0] != x[1] for x in zip(t,s[i:])]))
print(a)

S,T=open(0);print(min(sum(c!=d for c,d in zip(S[i:],T[:-1]))for i in range(len(S)-len(T)+1)))

s=list(input())
t=list(input())
ans=10**3+1
for i in range(len(s)-len(t)+1):
  count=0
  for j in range(len(t)):
    if s[i+j]!=t[j]:
      count+=1
  ans=min(count,ans)
print(ans)

S = input()
T = input()

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

cnt_min = M
for i in range(N - M + 1):
    count = 0
    for j in range(M):
        if S[i + j] != T[j]:
            count += 1
    if count < cnt_min:
        cnt_min = count

print(cnt_min)

S = input()
T = input()
max_count = 0
for i in range(len(S)-len(T)+1):
    s = S[i:i+len(T)]
    count = 0
    for j in range(len(T)):
        if s[j] == T[j]:
            count = count + 1
    if max_count <= count:
        max_count = count
        ans = len(T) - count
print(ans)


s = input()
t = input()
s_len = len(s)
t_len = len(t)
counter = 0
count_max = 0
for i in range(s_len - t_len + 1):
    for j in range(t_len):
        if s[i + j] == t[j]:
            counter += 1
            if counter > count_max:
                count_max = counter
    counter = 0
print((t_len - count_max))


# 2つの文字列S,Tを標準入力として受け取る
a = [str(input()) for i in range(2)]
S = a[0]
T = a[1]

# SとTの文字数をlength_S, length_Tとする
length_S = len(S)
length_T = len(T)

# 文字列SとTを1文字ずつ格納したリストl_S、l_Tを準備する。
l_S = [str(x) for x in list(str(S))]
l_T = [str(y) for y in list(str(T))]

# Sの部分文字列sを作り、リストl_sに格納
l_s = []
for i in range(length_S - length_T + 1):
    s = l_S[i:i + length_T]
    l_s.append(s)

l_b = []

for j in range(length_S - length_T + 1):
    l_a = []
    num1 = 0
    for i in range(length_T):
        if l_T[i] != l_s[j][i]:
            num1 += 1
        l_a.append(num1)
    l_b.append(l_a)

l_c = []
for i in range(length_S - length_T + 1):
    num2 = l_b[i][-1]
    l_c.append(num2)

ans = min(l_c)
print(ans)

S = input()
T = input()

max_match = 0
temp_match = 0

for i in range(len(S) - len(T) + 1):
    for j in range(len(T)):
        if S[i+j] == T[j]:
            temp_match += 1
    if temp_match > max_match:
        max_match = temp_match
    temp_match = 0

print(len(T) - max_match)

s = input()
t = input()

string_list = []
for i in range(len(s)-len(t)+1):
    string_list.append(s[i:i+len(t)])
    
count = 0
max_value = 0
for j in range(len(string_list)):
    for i in range(len(t)):
        if(string_list[j][i] == t[i]):
            count += 1
        if(max_value<count):
            max_value = count
    count = 0
    
print(len(t)-max_value)

import math
prime = [True for i in range(10**6+1)]
def SieveOfEratosthenes(n): 
	p = 2
	while (p * p <= n): 
		if (prime[p] == True):
			for i in range(p * p, n+1, p): 
				prime[i] = False
		p += 1

def __starting_point():
	s = str(input())
	s1 =str(input())
	c = -10**9
	con = 0
	F = 0
	for i in range(0, len(s)):
		con = 0
		if len(s)-i>=len(s1):
			F = i
			for j in range(0, len(s1)):
				if s[F]==s1[j]:
					con+=1
				F+=1
		c=max(c,con)

	print((len(s1)-c))



__starting_point()

S=input()
T=input()
L=len(S)-len(T)
b=0
if L>0:
  a=[0]*L
  for i in range(L):
    for j in range(len(T)):
      if S[j+i]==T[j]:
        a[i]=a[i]+1        
  A=sorted(a,reverse=True)
  print(len(T)-A[0])
  
if L==0:
  for l in range(len(S)):
    if S[l]==T[l]:
      b=b+1
  print(len(T)-b)

S = input()
T = input()
len_T = len(T)
ans_min_change_word = len_T
for i in range(len(S)-len_T+1):
  tmp_change_word = 0
  for j in range(len_T):
    if S[i+j]!=T[j]: tmp_change_word += 1    
  ans_min_change_word = min(ans_min_change_word, tmp_change_word)
print(ans_min_change_word) # (๑•ૅㅁ•๑)

def main():
    
    S = input()
    T = input()
    
    min = len(T)
    
    for i in range(len(S)-len(T)+1):
        cnt = 0
        desS = S[i:i+len(T)]
        
        for j in range(len(T)):
            if desS[j] == T[j]:
                cnt+=1
        
        if min > len(T)-cnt:
            min = len(T)-cnt
                
    print(min)
    
    
def __starting_point():
    main()
__starting_point()

# -*- coding utf-8 -*-

MOD = 10 ** 9 + 7

S = input()
T = input()

ans = len(T)
for i in range(len(S) - len(T) + 1):
    match = 0
    for j in range(len(T)):
        if T[j] == S[i + j]:
            match += 1
    ans = min(ans, len(T) - match)


print(ans)


s = [x for x in input()]
t = [x for x in input()]
u = list()
for i in range(len(s) - len(t) + 1):
    count = 0
    for j in range(len(t)):
        if s[i+j] == t[j]:
            continue
        if s[i+j] != t[j]:
            count += 1
    u.append(count)
u.sort()
print(u[0])

def compare(s1, t1):
    count = 0
    for a, b in zip(s1, t1):
        if a != b:
            count += 1
    return count

s = input()
t = input()
ans = 1001

for i in range(len(s) - len(t) + 1):
    ret = compare(s[i:], t)
    ans = min(ret, ans)
print(ans)


S = input()
T = input()

for i in range(len(S) - len(T) + 1):
    tmp = 0
    for j in range(len(T)):
        if S[i + j] != T[j]: tmp += 1
    ans = tmp if i == 0 else min(tmp, ans)
print(ans)

s = input()
t = input()
min = 10000
for i in range(len(s)-len(t)+1):
  count = 0
  for j in range(len(t)):
    if(s[i+j] != t[j]):
      count+=1
  if(count < min):
      min = count
print(min)

s = input()
t = input()
ans = 10000
for i in range(len(s) - len(t) + 1):
    score = 0
    u = s[i:i + len(t)]
    for j in range(len(t)):
        if u[j] != t[j]:
            score += 1
    ans = min(ans, score)
print(ans)

S = input()
T = input()

ans = len(S)
for i in range(len(S) - len(T) + 1):
    count = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            count += 1
    ans = min(ans, count)
print(ans)

a=input()
b=input()
c = len(a)-len(b)
d=[]
for i in range(len(a)-len(b)+1):
    a[i:i+len(b)]
    count = 0
    for j in range(len(b)):
        if a[i:i+len(b)][j] == b[j]:
              count +=1
    d.append(len(b)-count)
print(min(d))    

s = input()

t = input()

ans = []

for i in range(len(s) - len(t) + 1):
    l = 0
    for j in range(len(t)):
        if s[i + j] != t[j]:
            l += 1

    ans.append(l)

print((min(ans)))


s = list(input())
t = list(input())

n = len(s) - len(t) + 1

ans = 0

for i in range(n):
    count = 0
    for g in range(len(t)):
        if s[g + i] == t[g]:
            count += 1
    if count >= ans:
        ans = count

print(len(t) - ans)

s,t=input(),input()
ls=len(s)
lt=len(t)
ans=1000000000000
for i in range(ls-lt+1):
    ans_sub=0
    for j in range(lt):
        if t[j]!=s[i+j]:
            ans_sub+=1
    ans=min(ans,ans_sub)
print(ans)

import math
prime = [True for i in range(10**6+1)]
def SieveOfEratosthenes(n): 
	p = 2
	while (p * p <= n): 
		if (prime[p] == True):
			for i in range(p * p, n+1, p): 
				prime[i] = False
		p += 1

def __starting_point():
	s = str(input())
	s1 =str(input())
	c = -10**9
	con = 0
	F = 0
	for i in range(0, len(s)):
		con = 0
		if len(s)-i>=len(s1):
			F = i
			for j in range(0, len(s1)):
				if s[F]==s1[j]:
					con+=1
				F+=1
		c=max(c,con)

	print((len(s1)-c))



__starting_point()

s = input()
t = input()

val = 1000

for i in range(len(s)-len(t)+1):
    cnt = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            cnt += 1
    val = min(val,cnt)

print(val)

s = input()
t = input()

val = 10000

for i in range(len(s)-len(t)+1):
    cnt = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            cnt += 1
    val = min(val,cnt)

print(val)

s = input()
t = input()
ans=10**4
for a in range(len(s)-len(t)+1):
    tmp=0
    for b in range(len(t)):
        if s[a+b] == t[b]:
            tmp+=1
    ans=(min(ans, len(t)-tmp))
print(ans)

S = input()
T = input()
 
ans = len(S)
for i in range(len(S)-len(T)+1):
  cnt = 0
  for j in range(len(T)):
    if(S[i+j] != T[j]):
      cnt += 1
  ans = min(ans, cnt)
print(ans)

s = input()
t = input()
ans = 10 ** 5
n = len(s)
for i in range(n - len(t) + 1):
    cnt = 0
    for j in range(len(t)):
        if s[i + j] != t[j]:
            cnt += 1
    ans = min(ans, cnt)

print(ans)

s = input()
t = input()
sl = len(s)
tl = len(t)
ans = 10**9
for i in range(sl-tl+1):
    cnt = 0
    for j in range(tl):
        if s[i+j] != t[j]:
            cnt += 1
    ans = min(ans, cnt)
print(ans)

S = input()
T = input()
lenS = len(S)
lenT = len(T)
MIN = float('inf')
for i in range(lenS):
    tmpS = S[i:i+lenT]
    if len(tmpS) != lenT:
        continue
    count = 0
    for i in range(lenT):
        if tmpS[i] != T[i]:
            count += 1
    MIN = min(MIN,count)
print(MIN)

s = input()
t = input()
x = len(s)
y = len(t)
ans = 10000
for i in range(x):
  if(i > x - y):
    break
  tm = 0
  for j in range(0, y):
    if(s[i + j] != t[j]):
      tm += 1
  ans = min(tm ,ans)
print(ans)


S = input()
T = input()

n = len(S) - len(T) + 1
min = 1000

if T in S:
  print((0))

else:
  for i in range(n):
    tmp = 0
    for j in range(len(T)):
      if S[i+j] != T[j]:
        tmp += 1
    if tmp < min:
      min = tmp
  print(min)


S=input()
T=input()

ans=10**9

for i in range(len(S)-len(T)+1):
  ans_sub=0
  for j in range(len(T)):
    if T[j]!=S[i+j]:
      ans_sub+=1
  ans=min(ans,ans_sub)
print(ans)

s=list(input())
t=list(input())

ss=len(s)
tt=len(t)

ans=tt
for i in range(ss-tt+1):
  
  u=s[i:i+tt]
  cnt=0
  for j in range(tt):
    if u[j]==t[j]:
      cnt+=1
      ans_=tt-cnt
      ans=min(ans,ans_)
print(ans)

s = input()
t = input()

val = 1000

for i in range(len(s)-len(t)+1):
    cnt = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            cnt += 1
    val = min(val,cnt)

print(val)

S = input()
T = input()

num = [0] * len(S) #ここに、被った文字数を格納しておく。リストの中で一番高い数字が、一番多く被っている単語数になる

for i in range(len(S)-len(T)+1):
    for t in range(len(T)):
        if S[i+t] == T[t]:
            num[i] += 1

print(len(T)-max(num))

import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    S = input()
    T = input()
    answer = INF
    for i in range(len(S) - len(T) + 1):
        tmp = 0
        for j in range(len(T)):
            if S[i + j] != T[j]:
                tmp += 1
        answer = min(answer, tmp)
    print(answer)


def __starting_point():
    main()

__starting_point()

S = input()
T = input()

ans = len(T)

# Sの何文字目から調べるかを全探索
for start in range(0, len(S) - len(T) + 1):
  diff = 0
  for i in range(0, len(T)):
    if T[i] != S[start + i]:
      diff += 1
  if ans > diff:
    ans = diff
print(ans)

s=input()
t=input()
ans=100000
for i in range(len(s)-len(t)+1):
    score=0
    U=s[i:i+len(t)]
    for j in range(len(t)):
        if(U[j]!=t[j]):
            score+=1
    ans=min(ans,score)
print(ans)

S=input()
T=input()

count=0
m=len(T)
l=len(S)-len(T)
for i in range(0,l+1):
	for j in range(0,len(T)):
		if S[j+i]!=T[j]:
			count+=1

	if m>count:
		m=count
	count=0

print(m)






import numpy as np

def __starting_point():

    s = input()
    t = input()
    
    min_diff = 9999
    len_s = len(s)
    len_t = len(t)
    for i in range(len_s - len_t +1):
        count = 0
        for j in range(len_t):
            if t[j] is not s[i+j]:
                count += 1
        min_diff = min(count, min_diff)

    print(min_diff)
__starting_point()

s = input()
t = input()
n = len(t)
out = 2000
for i in range(len(s) - n + 1):
  p = s[i:i+n]
  count = 0
  for j in range(n):
    if t[j] != p[j]:
      count += 1
  if count < out:
    out = count
print(out)

def main():
    S = input()
    T = input()
    size = len(T)
    count = 10000
    for i in range(len(S)-size+1):
        x = 0
        for j in range(size):
            if S[i+j] != T[j]:
                x+=1
        count = min(count,x)
    print(count)              

def __starting_point():
    main()


__starting_point()

S=str(input())
T=str(input())
if T in S:
  print((0))
  return
max_char_cnt,substr=0,""
for i in range(len(S)-len(T)+1):
  substr=S[i:i+len(T)]
  same_char_cnt=0
  for s,t in zip(substr,T):
    if s==t:
      same_char_cnt+=1
  max_char_cnt=max(max_char_cnt,same_char_cnt)
  if len(T)-max_char_cnt==1:
    break
print((len(T)-max_char_cnt))


s,t=input(),input()
ans = len(t)
for i in range(len(s)-len(t)+1):
	s2 = s[i:i+len(t)]
	c = 0
	for j in range(len(s2)):
		if (s2[j] != t[j]):
			c += 1
	ans = min(ans, c)
print(ans)

s = list(input())
t = list(input())
d = 0
for a in range(len(s)-len(t)+1):
    c = 0
    for b in range(len(t)):
        if s[a+b] == t[b]:
            c = c + 1
    if c > d:
        d = c
print(len(t)-d)

import sys
readline = sys.stdin.readline

S = readline().rstrip()
T = readline().rstrip()

ans = 10 ** 10
for s_ind in range(len(S)):
  if s_ind + len(T) > len(S):
    break
  change = 0
  for t_ind in range(len(T)):
    if T[t_ind] != S[s_ind + t_ind]:
      change += 1
      if change > ans:
        break
  if ans > change:
    ans = change

print(ans)

s = input()
t = input()

ans = 1000000

for i in range(len(s) - len(t) + 1):
    cnt = 0
    for j in range(len(t)):
        if s[i + j] != t[j]:
            cnt += 1
    ans = min(ans, cnt)
print(ans)


s = input()
t = input()

ans = len(t)

for i in range(0, len(s) - len(t) + 1):
  diff = 0
  for j in range(0, len(t)):
    if t[j] != s[i+j]:
      diff += 1
  ans = min(diff, ans)
  
  
print(f"{ans}")

S = input()
T =input()

ans =len(T)

for start in range(len(S)-len(T)+1):
    diff = 0
    for i in range(len(T)):
        if T[i] != S[start+i]:
            diff += 1

    ans =min(ans,diff)
print(ans)

S=input()
T=input()
if T in S:
  print(0)
  return
max_same_char_cnt,substr=0,""
for i in range(len(S)-len(T)+1):
  substr=S[i:i+len(T)]
  same_char_cnt=0
  for s,t in zip(substr,T):
    if s==t:
      same_char_cnt+=1
  max_same_char_cnt=max(max_same_char_cnt,same_char_cnt)
  if len(T)-max_same_char_cnt==1:
    break
print(len(T)-max_same_char_cnt)

s = input()
t = input()
score = 1000

for i in range(len(s)-len(t) + 1):
  tmp = 0
  for j in range(len(t)):
    if s[i+j] != t[j]:
      tmp += 1
  score = min(score,tmp)
  
print(score)

import sys

S = input()
T = input()

ans = len(T)
for i in range(len(S)-len(T)+1):
    count = 0
    for j in range(len(T)):
        if S[i+j] == T[j]:
            count += 1
    ans = min(ans, len(T)-count)

print(ans)

S = input()
T = input()


ans = 100000  # 適当に1001以上にを初期値にしておきます

# Tが1文字のときlen(S)回、2文字のときlen(s) -1回....なので,
# les(S)-len(T)+1回です
for i in range(len(S) - len(T) + 1):
    score = 0
    U = S[i:i + len(T)]  # Sのi文字目から連続するlen(T)文字を,Uとします
    for j in range(len(T)):
        if U[j] != T[j]:
            score += 1
    ans = min(ans, score)

print(ans)


s=input()
t=input()
ls=len(s)
lt=len(t)
ans=ls
for i in range(ls-lt+1):
    cnt=0
    for j in range(lt):
        if s[i+j]!=t[j]:
            cnt+=1
    ans=min(ans,cnt)
            
print(ans)

S = list(input())
T = list(input())

ans = 0
for i in range(len(S)):
    s = S[i:]
    if len(s) < len(T):
        break
    tmp = 0
    for j in range(len(T)):
        if s[j] == T[j]:
            tmp += 1
    ans = max(ans, tmp)

print(len(T) - ans)

s = list(input())
t = list(input())
A = 10000
for i in range(len(s) - len(t) +1):
    u = s[i : i+len(t)]
    a = 0
    for j in range(len(t)):
        if u[j] != t[j]:
            a += 1
    A = min(A,a)
print(A)

s = input()
t = input()

ans_list = []

for i in range((len(s) - len(t)) + 1):
    u = s[i:len(t) + i]
    check_count = 0
    for a, b in zip(u, t):
        if a != b:
            check_count += 1
    ans_list.append(check_count)

print((min(ans_list)))


S=input()
T=input()
lens=len(S)
lent=len(T)
mincnt=lent


if lens==lent:
    if S==T:
        mincnt=0
    else:
        cnt=0
        for i in range(lent):
            if S[i]!=T[i]:
                cnt+=1
        mincnt=cnt
else:
    for i in range(lens-lent):
        cnt=0
        for j in range(lent):
            if S[i+j]!=T[j]:
                cnt+=1
        if cnt<mincnt:
            mincnt=cnt

print(mincnt)

S = input()
T = input()
ans = len(T)

for i in range(len(S) - len(T) + 1):
    cnt = len(T)
    for j in range(len(T)):
        if S[i+j] == T[j]:
            cnt -= 1
    ans = min(ans, cnt)
    
print(ans)

import sys
input = sys.stdin.readline
s = str(input()).replace('\n', '')
t = str(input()).replace('\n', '')

ans = len(t)

for i in range(len(s)-len(t)+1):
  diff = 0
  for j in range(len(t)):
    if t[j] != s[i+j]:
      diff += 1
  if ans > diff:
    ans = diff
print(ans)

#a = list(map (int,input().split()))
s = str(input())
t = str(input())
box =[]
for i in range(len(s)-len(t)+1):
    a = 0
    for j in range(len(t)):
        if t[j] != s[j+i]:
            a+=1
    box.append(a)
print((min(box)))


S = input()
T = input()
ma = 0
match = 0
for i in range(len(S)-len(T)+1):
  match = 0
  for j in range(len(T)):
    if S[i+j] == T[j]:
      match+=1
  ma = max(ma,match) 
print(len(T)-ma)

S = list(input())
T = list(input())
ans = len(T)
for i in range(len(S) - len(T) + 1):
    tot = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            tot += 1
    ans = min(ans, tot)
print(ans)

s = input()
t = input()

min_cnt = 10000

for i in range(len(s)-len(t)+1):
    cnt = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            cnt += 1
    if cnt < min_cnt:
        min_cnt = cnt

print(min_cnt)


s = input()
t = input()
if t in s:
    print(0)
    return
r=0
for i in range(0,len(s)-len(t)+1):
    sub_str = s[i:i+len(t)]
    c=0
    for a,b in zip(sub_str,t):
        if a==b:
            c+=1
    r = max(r,c)
#     print(f'c={c}')
    if r == len(t)-1:
        break
print(len(t) - r)

import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

INF = inf
MOD = 1000000007

s = input()
t = input()

tmp = 0
res = 0

res = INF
ls = len(s)
lt = len(t)
for i in range(ls - lt + 1):
    tmp = 0
    for j in range(lt):
        if t[j] != s[i + j]:
            tmp += 1
    res = min(res, tmp)

print(res)


s = input()
t= input()
len_s = len(s)
len_t =len(t)
# print(len_s, len_t)
ini=0
l_cnt = []
for i in range(len_s-len_t+1):
  cut = s[i: i+len_t]
  # print(cut)
  cnt = 0
  for i, w in enumerate(t):
    if w != cut[i]:
      cnt += 1
  l_cnt.append(cnt)
  # print(cnt)

print(min(l_cnt))

s = str(input())
t = str(input())
ans = 10000

for i in range(len(s)-len(t)+1):
    tmp = 0
    u =s[i:i+len(t)]
    for j in range(len(t)):
        if u[j]!=t[j]:
            tmp +=1
    ans=min(ans,tmp)
print(ans)

s = input()
t = input()
if t in s:
  print(0)
  return
ns = len(s)
nt = len(t)
ans = nt
k = ns - nt
for i in range(k+1):
  hoge = s[i:i+nt]
  c = 0
  for j in range(nt):
    if hoge[j] != t[j]:
      c += 1
  ans = min(c,ans)
print(ans)

S = input()
T = input()

ans = 1000
for i in range((len(S) - len(T)  + 1)):
    ans_sub = 0
    for j in range(len(T)):
        if T[j] != S[i+j]:
            ans_sub += 1
    ans = min(ans, ans_sub)

print(ans)


s=input()
t=input()

mn=1001
for i in range(len(s)-len(t)+1):
    sm=0
    for j in range(len(t)):
        if s[i+j]!=t[j]:
            sm+=1
    if sm<mn : mn=sm
print(mn)

S = input()
T = input()

for i in range(len(S)-len(T) + 1):
    tmp = 0
    for j in range(len(T)):
        if S[i + j] != T[j]: tmp += 1
    ans = tmp if i == 0 else min(tmp,ans)

print(ans)


S = input()
T = input()

ans = 10**9
for i in range(len(S)-len(T)+1):
    tmp = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            tmp += 1
        
    ans = min(tmp, ans)

print(ans)

S = input()
T = input()

# 仮の答え
answer = len(S)

def calculate_difference(word_s, word_t):
    return sum([ 0 if word_s[i] == word_t[i] else 1
                 for i in range(len(word_s))] )

# S の何文字目にTを重ねるか
for s_index in range(0, len(S) - len(T) + 1):
    s_substring = (S[s_index: s_index + len(T)])
    answer = min(answer, calculate_difference(s_substring, T))
    
print(answer)


s = input()
t = input()

ans = len(t)
for i in range(len(s)-len(t)+1):
	cnt = 0
	for j in range(len(t)):
		if s[i+j] != t[j]:
			cnt += 1
	ans = min(ans, cnt)
print(ans)


def compare_s(s1, s2):
    ret = 0
    for i1, i2 in zip(s1, s2):
        if i1 != i2:
            ret += 1
    return ret


s = input()
t = input()
min_ = 1001

for i in range(len(s) - len(t) + 1):
    temp = compare_s(t, s[i:])
    if temp < min_:
        min_ = temp

print(min_)

S = input()
T = input()
data = []

for i in range(len(S) - len(T) + 1):
    count = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            count += 1
    data.append(count)
        
print((min(data)))


import itertools

def main():
  ans = 0 
  ans1 = []
  s = input()
  t = input()
  #print('s:',s,'t:',t)
  ss = len(s)
  ts = len(t)
  for i in range(ss-ts+1):
    #print(s[0+i:ts+i])
    for j,x in enumerate(s[0+i:ts+i]):
      #print(x,t[j])
      if t[j]==x:
        #print('hit',x,t[j])
        ans +=1 

    ans1.append(ans)  
    ans = 0    
  print(ts-max(ans1))  
  
  
def __starting_point():
    main()
__starting_point()

from sys import stdin
S = stdin.readline().rstrip()
T = stdin.readline().rstrip()
ls, lt = len(S), len(T)
ans = ls
for i in range(0, ls-lt+1):
    diff = 0
    for j in range(lt):
        if T[j] != S[i+j]:
            diff += 1
    ans = min(ans, diff)
print(ans)

s = input()
t = input()
 
ans = len(t)
for i in range((len(s) - len(t)) + 1):
  count = 0
  a = s[i : i + len(t)]
  for j in range(len(t)):
    if a[j] != t[j]:
      count += 1
  ans = min(ans, count)

print(ans)


s = input()
t = input()
ans = len(t)

for i in range(len(s) - len(t) + 1):
    w = 0
    # print("--"*t_length)
    #print(s[i:i+t_length], t, sep="\n")

    for k in range(len(t)):
        if s[i+k] != t[k]:
            w += 1
        """
            print("x", end="")
        else:
            print(" ", end="")
        """
    ans = min(ans, w)
    #print("\nw =", w, "ans = ", ans)

print(ans)


S = input()
T = input()

ans = len(T)

for s in range(len(S)):
  if len(S) - s < len(T):
    break
  count = 0
  for t in range(len(T)):
    if S[s + t] != T[t]:
      count += 1
      
  ans = min(count, ans)
  
print(ans)

s = list(input())
t = list(input())

min = len(t)

for i in range(0,len(s) - len(t)  + 1):
    count = 0
    for j in range(0,len(t)):
        if s[i + j] != t[j]:
            count += 1

    if count < min:
        min = count
print(min)