Message

Interview

Time limit2sMemory limit1024 MB

Summary

Given strings c and s, find the largest k such that c repeated k times is a subsequence of s.

Level: Easy3 of 10
Topics: Greedy, String
Solved: No attempts yet

Problem

While traveling, Doctor Strange ran into a hard problem. He must decrypt the string $s$ that arrived in his email. The message was encrypted as follows. A string $c$ is written some number of times (possibly zero). Then letters of the message are inserted between arbitrary letters of the resulting string, possibly several letters at once, and the result is $s$ .

Doctor Strange has already figured out which string $c$ was used. To decrypt the message, he needs the maximum number of times $c$ could have been written during encryption.

Input

The first line contains the string $c$ . The second line contains the string $s$ . Each string consists of uppercase and lowercase Latin letters. The length of each string does not exceed $10^6$ .

Output

Print a single integer, the answer to the problem.

Examples1

Example 1
Input
```
ab
abacabaaacbb
```
Expected output
```
3
```