Chuỗi ARN

Trong phòng thí nghiệm, các nhà khoa học đang nghiên cứu về gen của một chuỗi ARN đặc biệt được mã hoá bằng một xâu $S$ gồm các kí tự 'A', 'U', 'G', 'X'. Họ muốn cắt từ chuỗi ARN đó một mạch (được mã hoá bằng xâu $X$) cho trước.

Mỗi đoạn mạch cắt ra là một đoạn gồm các kí tự liên tiếp của $S$ bằng đúng $X$. Các đoạn cắt ra không được dùng chung kí tự nào của $S$. Sau khi cắt, các phần còn lại của chuỗi không được nối lại với nhau để cắt tiếp.

Yêu cầu: từ chuỗi ARN $S$ có thể cắt được ra tối đa bao nhiêu đoạn mạch $X$.

Dữ liệu vào

• Dòng đầu tiên gồm một xâu kí tự $S$ mô tả chuỗi ARN;
• Dòng thứ hai gồm một xâu kí tự $X$ mô tả đoạn mạch cần cắt ra.

Các xâu chỉ gồm các kí tự 'A', 'U', 'G', 'X' và độ dài các xâu không quá ${10}^3$ kí tự.

Dữ liệu ra

Một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc

• $1\le |S|,|X|\le {10}^3$.
• $S$ và $X$ chỉ gồm các kí tự 'A', 'U', 'G', 'X'.

Ví dụ