Duck Contest

Space Ducks

Program time limit: 1 seconds

Program memory limit: 256 MB

Zitian the space explorer has embarked on a journey to find a habitable planet for the next generation of humanity. As he travelled past the Milky Way, he entered a zone called the Cosmic Pond Mallards (CPM). Nearby, a group of ducks were trying to communicate with him.

The ducks made many different quacks, and Zitian noticed that one quack seemed to appear more often than the others. In his hurry to record the ducks' sounds, he forgot to put spaces between the quacks. Now he needs your help to determine how many times the word $S_2$ appears in the recorded string $S_1$.

Input

  • The first line contains a string $S_1$, Zitian's recorded sound.
  • The second line contains a string $S_2$, the word Zitian wants to count.

You should read from standard input.

Constraints

  • $1 \le \vert S_1 \vert, \vert S_2 \vert \le 10^6$
  • The strings $S_1$ and $S_2$ consist only of lowercase English letters.

Output

  • Output the number of times $S_2$ appears in $S_1$.

Overlapping occurrences should be counted.

You should write to standard output.

Sample Input 1

quaackquackquuackqquack
quack

Sample Output 1

2

Explanation 1

  • The substring starting at index $6$ is "quack".
  • The substring starting at index $18$ is "quack".

Sample Input 2

aabaabaaaaaaabababaaab
aab

Sample Output 2

4

Explanation 2

  • The substring starting at index $0$ is "aab".
  • The substring starting at index $3$ is "aab".
  • The substring starting at index $11$ is "aab".
  • The substring starting at index $19$ is "aab".

Scoring

Your program will be tested on the sample cases and several hidden cases. If it produces the correct output for all test cases, it will be considered correct. Recall that your final score for this problem is the score of your highest-scoring submission.

Submit

The contest ended at 8:16 p.m. AEST on Thursday 2nd July. All submissions will be unofficial .