Problem Statement

Given are strings $S$ and $T$ consisting of 0 and 1. We will change some of the characters in $T$ so that $T$ becomes a substring of $S$. How many characters do we need to change at least?

What is a substring? $T$ is said to be a substring of $S$ when some contiguous part of $S$ matches $T$. For example, 000 is a substring of 10001, while 11 is not.

Constraints

• Each of $S$ and $T$ consists of 0 and 1.
• $1 ≤ |T| ≤ |S| ≤ 10^6$

Input

Input is given from Standard Input in the following format:

S
T

Output

Print the answer.