Document Search

You want to count how many times a word appears in a document made only of lowercase English letters and spaces. However, two counted occurrences must not overlap, even by one character.

For example, if the document is abababa and the word is ababa, the word can start at position 0 or at position 2. These two occurrences overlap, so they cannot both be counted.

Given the document and the word to search for, compute the maximum number of non-overlapping occurrences of the word.

The first line contains the document. Its length is at most 2500.

The second line contains the word to search for. Its length is at most 50.

The document and the word consist only of lowercase English letters and spaces.

Print the maximum number of times the word can appear in the document without overlapping.