Period

Given two strings $A$ and $B$ over an alphabet $\Sigma$, the edit distance between $A$ and $B$ is the minimum number of edit operations needed to turn $A$ into $B$. There are three edit operations:

• change: replace one character of $A$ with a single character of $B$.
• deletion: delete one character from $A$.
• insertion: insert one character of $B$ into $A$.

For example, the figure below shows that the edit distance between $A = abcdefg$ and $B = ahcefig$ is $3$: a change (replacing b with h), a deletion (deleting d), and an insertion (inserting i).

The exact period of a repetitive string is defined as follows. A string $p$ is the exact period of a string $x$ if $x$ can be written as $x = p^k$ with $k \ge 1$, where $p$ is the shortest such string. For example, if $x = abababab$ then $x = (abababab)^1 = (abab)^2 = (ab)^4$, so $ab$ is the exact period of $x$.

An approximate period is defined similarly. Given strings $x$ and $y$, suppose $x$ is split into non-empty substrings $p_1, p_2, \dots, p_t$ so that $x = p_1 \cdot p_2 \cdots p_t$. If the edit distance between $y$ and every substring $p_i$ is at most an integer $k$, then $y$ is called a $k$-approximate period of $x$.

Given $x$ and $y$, find the minimum $k$ such that $y$ is a $k$-approximate period of $x$. For example, if $x = abcdabcabb$ and $y = abc$, then $x$ can be split as $x = p_1 \cdot p_2 \cdot p_3 = abcd \cdot abc \cdot abb$, and the edit distances between $y = abc$ and abcd, abc, abb are $1$, $0$, and $1$. The largest of these is $1$, so $y$ is a $1$-approximate period of $x$ and the minimum $k$ is $1$.

The input is read from standard input. The first line contains the number of test cases $T$. Each test case is given on two lines: the first line contains the string $y$ and the second line contains the string $x$. The length of $y$ satisfies $1 \le |y| \le 50$ and the length of $x$ satisfies $1 \le |x| \le 5000$. Both strings consist only of lowercase English letters (the alphabet $\Sigma$).

Write to standard output. For each test case, print exactly one line containing the minimum integer $k$ such that $y$ is a $k$-approximate period of $x$.