p02962 AtCoder Beginner Contest 135 - Strings of Eternity
Given are two strings s and t consisting of lowercase English letters. Determine if the number of non-negative integers i satisfying the following condition is finite, and find the maximum value of such i if the number is finite.

* There exists a non-negative integer j such that the concatenation of i copies of t is a substring of the concatenation of j copies of s.

Constraints

* 1 \leq |s| \leq 5 \times 10^5
* 1 \leq |t| \leq 5 \times 10^5
* s and t consist of lowercase English letters.

Input

Input is given from Standard Input in the following format:


s
t


Output

If the number of non-negative integers i satisfying the following condition is finite, print the maximum value of such i; if the number is infinite, print `-1`.

Examples

Input

abcabab
ab


Output

3


Input

aa
aaaaaaa


Output

-1


Input

aba
baaab


Output

0
```python
# AOJ ALDS1_14_B "String Search"
# returns i s.t. S[i+j] = T[j] for 0 <= j < len(T)

def RollingHash(S, T, ls):
    if len(S) < len(T):
        return []
    # gcd(h, b) = 1
    h = 10**11+7
    b = 10**7+7
    L = len(T)

    bL = 1
    for i in range(L):
        bL = bL * b % h

    hashS = 0
    for i in range(L):
        hashS = (hashS * b + S[i]) % h

    hashT = 0
    for i in range(L):
        hashT = (hashT * b + T[i]) % h
    
    correctIndexes = [0]*len(S)
    ret = 0
    if hashS == hashT:
        correctIndexes[0] = 1
    for j in range(len(S)-L):
        hashS = (hashS * b - S[j]*bL + S[L+j]) % h
        if hashS == hashT:
            tmp = correctIndexes[j+1-L] + 1
            correctIndexes[j+1] = tmp
            if tmp > ret: ret = tmp
    if ret*L > 2*ls:
        return -1
    return ret


import sys
input = sys.stdin.buffer.readline

S = input().rstrip()
T = input().rstrip()

ls = len(S)
lt = len(T)
S = S*((2*lt+3*ls-1)//ls)
ans = RollingHash(S, T, ls)
print(ans)
```