Given two strings – a text A and a pattern B, having lower-case alphabetic characters. You have to determine the number of occurrences of pattern B in text A as its substring. i.e. the number of times B occurs as a substring in A.

Problem Constraints

1 <= |B| <= |A| <= 105

Input Format

First argument is a string A






Second argument is a string B






Output Format

Return the number of occurrences.

Example Input

Input 1:






 A = "abababa"
 B = "aba"

Input 2:



 A = "mississipi"
 B = "ss"


Input 3:

 A = "hello" 
 B = "hi"





Example Output

Output 1:






Output 2:


Output 3:

Please signup/login to view answer.