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

$conn(“abc”,2)=”abcabc”$

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

例如 $`abdbec`$ 可以生成 $`abc`$，但是 $`acbbe`$ 不能生成 $`abc`$。

给定两个字符串 s1 和 s2，以及两个整数 n1 和 n2，求一个最大的整数 m，满足 $conn(conn(s2,n2),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