Ada the Ladybug is helping her friend who is biologist. He examines DNA. Actually he has a long DNA of one bug, consisting of adenine, cytosine, guanine and thymine and he wants to know whether another bug might be relative to first bug. A bug is relative to another bug if his his DNA has very low Hamming Distance with some substring of the first bug.

Your job is to find the lowest hamming distance between second DNA and any substring of first DNA.

Input

Input contains only two lines: first DNA (s) and second DNA (r).

It is true that 0 < |r| ≤ |s| ≤ 5*10⁵

|s| means leangth of string s.

All strings contains only A, C, T, and G .

Output

Print minimal Hamming Distance (the number of mismatched nucleobases) of any substring of s and r (the substring MUST have length |r|)

Example Inputs

ACTGACTGACTG
ACCG

AAAAAACCA
AAACA

ACGC
GGG

ACTTTG
TTTGA

ACTGACTGACTG
ACTG

Example Output

1

1

2

3

0

Inputs explanation

ACTGACTGACTG
AAAAAACCA
ACGC
ACTTTG
ACTGACTGACTG