Migrated from Lutece 2078 こんにちは

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

已知只包含小写字母的字符串$N,M$,请你求出有多少下标$i(0<=i<=|N|-|M|)$满足$N[i] = M[0],N[i + 1] = M[1],...,N[i + |M|-1] = M[|M|-1]$.

注：$|S|$表示字符串$S$的长度。

Input

第一行为一个字符串$N$.

第二行为一个字符串$M$.

$(1<=|M|<=|N|<=1000000)$

Output

满足题目要求的下标总数。

Samples

ababa
aba

2