题目描述

给定两个由小写英文字母组成的字符串$s$和$t$。判断满足以下条件的非负整数$i$的数量是否有限，并找出满足条件的最大$i$的值（如果数量有限）。

• 存在一个非负整数$j$，使得$t$的$i$个拷贝的串是$s$的$j$个拷贝的串的子串。

注意事项

• 字符串$a$是字符串$b$的子串，当且仅当存在一个整数$x$ $(0 \leq x \leq |b| - |a|)$，使得对于任意$y$ $(1 \leq y \leq |a|)$，有$a_y = b_{x+y}$。

• 我们假设零个字符串的连接是空字符串。根据上述定义，空字符串是任何字符串的子串。因此，对于任何两个字符串$s$和$t$，条件中的$i = 0$都满足。

约束条件

• $1 \leq |s| \leq 5 \times 10^5$
• $1 \leq |t| \leq 5 \times 10^5$
• $s$和$t$由小写英文字母组成。

输入

从标准输入读入输入数据。

输入数据的格式如下：

$s$ $t$

输出

如果满足以下条件的非负整数$i$的数量有限，则输出满足条件的最大$i$的值；如果数量无限，则输出-1。

示例输入 1

abcabab
ab

示例输出 1

3

$t$的三个拷贝的连接ababab是$s$的两个拷贝的连接abcabababcabab的子串，所以$i = 3$满足条件。

另一方面，$t$的四个拷贝的连接abababab不是任何数量的$s$的拷贝的连接的子串，所以$i = 4$不满足条件。

类似地，大于$4$的任何整数都不满足条件。因此，满足条件的非负整数$i$的数量是有限的，最大的$i$的值是$3$。

示例输入 2

aa
aaaaaaa

示例输出 2

-1

对于任意非负整数$i$，$t$的$i$个拷贝的连接是$s$的$4i$个拷贝的连接的子串。因此，存在无限多个满足条件的非负整数$i$。

示例输入 3

aba
baaab

示例输出 3

0

正如注意事项中所述，$i = 0$始终满足条件。