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

inputFormat

Input

Input is given from Standard Input in the following format:

s t

outputFormat

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

样例

aa
aaaaaaa

-1