Shortened Form

Time limit1sMemory limit512 MB

Summary

Find the smallest n such that S is a subsequence of T repeated n times, or -1 if no such n exists.

Level: Medium5 of 10
Topics: Greedy, String, Binary search, Two pointers
Solved: No attempts yet

Problem

A string A is a shortened form of a string B if A can be obtained by deleting zero or more characters from B without changing the order of the remaining characters. By this definition, B is a shortened form of itself. For example, ac, ab, aa, and aabc are shortened forms of aabc, while d, aaa, and ba are not.

You are given two strings S and T consisting only of lowercase English letters. Let Tn denote the string formed by concatenating n copies of T, where n is a positive integer. Find the smallest n for which S is a shortened form of Tn.

For example, if T = ac and S = caa, then T1 = T = ac, T2 = acac, and T3 = acacac, and n = 3 is the first value for which S is a shortened form of Tn.

Input

The first line contains the string S.

The second line contains the string T.

Output

Print the smallest n for which S is a shortened form of Tn. If Tn is not a shortened form of S for every n, print -1.

Constraints

S and T consist only of lowercase English letters (a - z).
The length of S is between 1 and 1 000 000.
The length of T is between 1 and 100 000.

Examples2

Example 1
Input
```
caa
ac
```
Expected output
```
3
```
Example 2
Input
```
cab
acca
```
Expected output
```
-1
```