Agitations

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Before the elections, there is always a period of agitation. Different parties hold rallies in city squares, constantly chanting slogans. One election day, Zenyk decided to take a walk around the city. While walking along the central streets of his hometown, he heard various slogans echoing from everywhere. However, he only heard the endings of the phrases, meaning that if they chanted "Слава Україні!", Zenyk might have heard "...ні" or "...країні".

Unfortunately, the agitators are not very creative people, and they constantly chant the same slogan. However, they are very persistent and chant this slogan many times in a row. Zenyk became curious about how many times they actually chanted this slogan.

You are given the slogan \(p\) that the agitators chanted. You are also given the string \(r\), which is the concatenation of the endings of the string \(p\) — everything that Zenyk heard. You need to determine the minimum number of times the slogan \(p\) had to be repeated so that Zenyk heard what he heard.

Input

The first line contains the string \(p\) — the slogan chanted by the agitators.

The second line contains the string \(r\) — the concatenation of everything Zenyk heard.

Each string consists exclusively of lowercase Latin letters.

Output

In a single line, print a single integer — the minimum number of endings of the string \(p\) required to form the string \(r\).

It is guaranteed that the result always exists, i.e., the string \(r\) can always be formed from the endings of the string \(p\).

Constraints

\(1 \le |p|, |r| \le 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
glorytoukraine ukraineaineaine	3

Notes

Zenyk heard ukraine, aine, aine.