题目描述

定义 $str = [s, n]$ 表示 $str$ 由 $n$ 个字符串 $s$ 连接构成。

例如，$str == [\texttt{abc}, 3] == \texttt{abcabcabc}$。 如果可以从 $s_2$ 中删除某些字符使其变为 $s_1$，则称字符串 $s_1$ 可以从字符串 $s_2$ 获得。

例如，根据定义，$s1 = \tt{abc}$ 可以从 $s2 = \tt{ab\red{dbe}c}$ 获得，仅需要删除红色标识的字符。

现在给你两个字符串 $s_1$ 和 $s_2$ 和两个整数 $n_1$ 和 $n_2$。由此构造得到两个字符串，其中 $str_1 = [s_1, n_1]$、$str_2 = [s_2, n_2]$。

请你找出一个最大整数 $m$，以满足 $str = [str_2, m]$ 可以从 $str_1$ 获得。

输入格式

本题有多组测试数据。测试数据不超过 $100$ 组。

对于每组测试数据，分为两行：

• 第一行输入字符串 $s_1$ 和整数 $n_1$；
• 第二行输入字符串 $s_2$ 和整数 $n_2$；

输出格式

对于每组测试数据，输出整数 $m$ 表示答案。

ab 2
acb 4
acb 1
acb 1

2
1

提示

数据保证，$s_1,s_2$ 全为小写字母构成，且 $1\leq |s_1|,|s_2| \leq 100$，$1\leq n_1,n_2\leq 10^6$，每个测试点的测试数据不超过 $100$ 组。