Đếm Lần Khớp

Một lần xuất hiện của xâu $P$ trong xâu $T$ là một đoạn ký tự liên tiếp của $T$ bằng đúng $P$. Các lần xuất hiện có thể chồng lấn nhau. Hãy đếm tổng số lần xuất hiện.

Input

• Dòng thứ nhất chứa xâu văn bản $T$.
• Dòng thứ hai chứa xâu mẫu $P$.

Output

• In một số nguyên là số lần $P$ xuất hiện trong $T$.

Constraints

• $1\le |T|,|P|\le 10^6$.
• Mỗi xâu chỉ gồm các chữ cái thường tiếng Anh.

Scoring

• Subtask $1$ ($50\%$ số điểm): $|T|,|P|\le 80$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

aaaaabaaaaa
aaa

6