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

见题面

见题面