定义 $conn(s,n)$ 为 n 个字符串 s 首尾相接形成的字符串，例如：

称字符串 a 能由字符串 b 生成，当且仅当从字符串 b 中删除某些字符后可以得到字符串 a。

例如“abdbec”可以生成“abc”，但是“acbbe”不能生成“abc”。

给定两个字符串 $s\_1$ 和 $s\_2$，以及两个整数 $n\_1$ 和 $n\_2$，求一个最大的整数 m，满足$conn(conn(s\_2,n\_2 ),m)$ 能由 $conn(s\_1,n\_1)$ 生成。

输入格式

输入包含多组测试数据。

每组数据由2行组成，第一行包含$s\_2,n\_2$，第二行包含$s\_1,n\_1$。

输出格式

对于每组数据输出一行表示答案m。

数据范围

$s\_1$ 和 $s\_2$ 长度不超过100，$n\_1$ 和 $n\_2$ 不大于 $10^6$。

输入样例：

ab 2
acb 4
acb 1
acb 1
aa 1
aaa 3
baab 1
baba 11
aaaaa 1
aaa 20

输出样例：

2
1
4
7
12

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解