Problem Description

Define $str = [s, n]$ to mean that $str$ is formed by concatenating the string $s$ exactly $n$ times.

For example, $str == [\texttt{abc}, 3] == \texttt{abcabcabc}$. If we can delete some characters from $s_2$ to make it become $s_1$, then we say that the string $s_1$ can be obtained from the string $s_2$.

For example, by definition, $s1 = \tt{abc}$ can be obtained from $s2 = \tt{ab\red{dbe}c}$, by only deleting the characters marked in red.

Now you are given two strings $s_1$ and $s_2$, and two integers $n_1$ and $n_2$. Based on them, we construct two strings: $str_1 = [s_1, n_1]$ and $str_2 = [s_2, n_2]$.

Please find the maximum integer $m$ such that $str = [str_2, m]$ can be obtained from $str_1$.

Input Format

This problem contains multiple test cases. There are at most $100$ test cases.

For each test case, there are two lines:

• The first line contains the string $s_2$ and the integer $n_2$.
• The second line contains the string $s_1$ and the integer $n_1$.

Output Format

For each test case, output the integer $m$ as the answer.

ab 2
acb 4
acb 1
acb 1

2
1

Hint

The testdata guarantees that $s_1$ and $s_2$ consist only of lowercase letters, and $1 \leq |s_1|, |s_2| \leq 100$, $0 \leq n_1, n_2 \leq 10^6$. For each test point, there are no more than $100$ test cases.

Translated by ChatGPT 5