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.

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³ kí tự.

Kết quả:

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

Ví dụ:

Input	Output	Giải thích
AUAUGXXAUGXGX AUGX	2	AUAUGXXAUGXGX
AAAAA AAA	1	AAAAA
AGAX U	0