#1371Period

★★★★

時間限制：2000 毫秒記憶體限制：64 MB

Given two strings A and B over an alphabet Σ, the edit distance between A and B is the minimum number of edit operations needed to convert A into B. The three edit operations are the following:

(i) change: replace one character of A by another single character of B.

(ii) deletion: delete one character from A.

(iii) insertion: insert one character of B into A.

For example, the following figure shows that the edit distance between the strings A=abcdefg and B=ahcefig is 3. The edit operations are a change (i.e., replacing b of A by h of B), a deletion (i.e., deleting d from A), and an insertion (i.e., inserting i of B into A).

Diagram showing A=abcdefg changed to B=ahcefig via a change, deletion, and insertion, edit distance 3

We now define a period of a repetitive string as follows: The string p is called the exact period of a string x if x can be written as x = p, where k ≥ 1 and p is the shortest string. For example, if x = abababab then x = (abababab) = (abab) = (ab). Thus, the string ab is the exact period of x.

範例輸入 1

3
abc
abcdabcabb
abab
abababababab
xyz
abcdefghikjlmn

範例輸出 1

1
0
3

Pro 專屬功能：查看這題在歷屆 CPE 出現過幾次 — 升級以解鎖.

UVa 1371 - Period｜CPE 題目線上練習與解題 | judge.

⁴

We define an approximate period similarly. Given two strings x and y, suppose that the string x is partitioned into substrings p_i, 1 ≤ i ≤ t, where p_i is not a null string, i.e., x = p₁ · p₂ · p₃ · · · p_t. If the edit distance between a string y and each substring p_i is less than or equal to an integer k, string y is called a k-approximate period of string x.

In this problem, given two strings x and y, we want to find the minimum k such that string y is a k-approximate period of string x. For example, suppose that two strings x = abcdabcabb and y=abc are given. Since x may be partitioned into x = p₁ · p₂ · p₃ = abcd · abc · abb and the edit distances between string y=abc and each substring abcd, abc, and abb equal to 1, 0, and 1, respectively, y is a 1-approximate period of x. Hence, the minimum k is one.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. For each test case, a string y is given in the first line and the string x is given in the next line. The length of string y is at least 1 and at most 50, the length of string x is at least 1 and at most 5000, and the alphabet Σ is the set of lowercase English characters.

Output

Your program is to write to standard output. Print exactly one line for each test case. Print the minimum integer value k such that string y is a k-approximate period of string x.