EIU Programming Practices and Exams

Vào năm XXXX, 2 cường quốc EIU và UIE đánh nhau dữ dội, ngày ZZ/YY/XXXX, tổng cục chỉ huy của EIU cần gửi quân lương được khóa bằng mật khẩu, mật khẩu chỉ có thể lấy từ mật thư và được đưa đi bằng đường khác. Để đề phòng bị cướp mật thư lộ mật khẩu, EIU đã mã hóa thư bằng cách chèn thật nhiều kí tự ngẫu nhiên vào. Mật khẩu là số lượng pattern nhiều nhất có thể lấy ra từ mật thư bằng cách xóa các kí tự không cần thiết (vị trí các kí tự không được phép thay đổi).
VD

Pattern: EIU

Mật thư: EIEUUIUUEIU

=> EI E U UIUU EIU =>EIUEIU => 2

hoặc EI E UU IU U EIU

Input

Dòng đầu là pattern. Dòng thứ hai là mật thư. (cả 2 không quá 10⁶ kí tự, bao gồm các kí tự thứ 32 đến 126 trong bảng mã ASCII)

Output

Một số nguyên duy nhất là mật khẩu.

Example

Input:
EIU
EIEUUIUUEIU
Output:
2