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 có thể cắt được ra tối đa bao nhiêu đoạn mạch \( X \) .

Input

• 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ự.

Output

• Một số nguyên duy nhất: số lần tối đa có thể cắt đoạn mạch \( X \).

Example

AUAUGXXAUGXGX
AUGX 

2

AAAAA
AAA

1

AGAX
U

0