题目描述

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

$\red {conn(“abc”,2)=”abcabc”}$

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

例如$\red {“abdbec”}$可以生成$\red {“abc”}$，但是$\red {“acbbe”}$不能生成$\red {“abc”}$。

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

输入格式

输入包含多组测试数据。

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

输出格式

对于每组数据输出一行表示答案$\red {m}$。

样例

输入样例

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

提示

$\red {s_1}$ 和 $\red {s_2}$ 长度不超过$\red {100， n_1}$ 和 $\red {n_2}$ 不大于 $\red {10 ^6}$ 。