Cho hai xâu ~X~ và ~Y~ chỉ gồm các kí tự in thường. Trong một thao tác, bạn có thể chọn một kí tự bất kì trên xâu ~X~ và xóa nó đi. Đếm số thao tác ít nhất để xâu ~Y~ không còn xuất hiện trong xâu ~X~ nữa.

Định nghĩa xâu ~A~ gọi là xuất hiện trong xâu ~B~ nếu tồn tại vị trí ~i~ (~1 \leq i \leq |B| - |A| + 1~) mà ~A_j = B_{i + j - 1} \forall j \in [1, |A|]~, ở đây mỗi kí tự được đánh chỉ số từ ~1~ từ trái qua phải và ~|t|~ là độ dài của xâu ~t~.

Input

Gồm ~3~ testcase, mỗi testcase trên hai dòng.

• Dòng đầu tiên chứa xâu ~X~ (~1\leq |X| \leq 10^4~).

• Dòng thứ hai chứa xâu ~Y~ (~1 \leq |Y| \leq 10^3~).

Output

Gồm ~3~ dòng, mỗi dòng in ra một số duy nhất là số thao tác ít nhất để xâu ~Y~ không còn xuất hiện trong xâu ~X~.

Sample Input 1

hhhhh
h
xywpywtddh
yw
cyapyaa
ya

Sample Output 1

5
2
2