Trong một hệ thống lưu trữ dữ liệu cổ, các thông điệp được ghi lại dưới dạng một chuỗi ký tự dài liên tục. Tuy nhiên, theo tài liệu còn sót lại, có một mẫu thông điệp đặc biệt được sử dụng nhiều lần trong bản ghi này.

Bạn được cung cấp: Một chuỗi ký tự dài biểu diễn bản ghi dữ liệu tổng thể Một chuỗi ký tự ngắn hơn biểu diễn mẫu thông điệp cần tìm

Do lỗi trong hệ thống cũ, các thông điệp có thể được ghi liền nhau, thậm chí chồng lấn một phần, vì vậy bạn cần kiểm tra mọi vị trí có thể trong bản ghi.

Nhiệm vụ của bạn là: Xác định có bao nhiêu đoạn liên tiếp trong bản ghi dữ liệu trùng khớp hoàn toàn với mẫu thông điệp. Hai lần xuất hiện được xem là khác nhau nếu chúng bắt đầu tại hai vị trí khác nhau trong bản ghi.

Input

Dữ liệu được đọc từ đầu vào chuẩn: Dòng thứ nhất chứa chuỗi ký tự S — bản ghi dữ liệu tổng thể. Dòng thứ hai chứa chuỗi ký tự T — mẫu thông điệp cần tìm. Thỏa mãn: ~1~ ≤ ~∣T∣~ ≤ ~∣S∣~ ≤ ~10^6~. Các chuỗi chỉ gồm ký tự chữ cái Latin.

Output

Ghi ra đầu ra chuẩn: Một số nguyên duy nhất — tổng số lần mẫu thông điệp xuất hiện trong bản ghi dữ liệu.

Example input 1

ababa
aba

Example output 1

2

Note 1

Mẫu aba xuất hiện tại: vị trí 1 vị trí 3 Hai lần xuất hiện này có thể chồng lấn, nhưng vẫn được tính riêng.