주기

알파벳 $\Sigma$ 위에서 정의된 두 문자열 $A$와 $B$에 대해, $A$와 $B$ 사이의 편집 거리는 $A$를 $B$로 바꾸는 데 필요한 최소 편집 연산 횟수이다. 편집 연산은 다음 세 가지이다.

• 교체(change): $A$의 한 문자를 $B$의 한 문자로 바꾼다.
• 삭제(deletion): $A$에서 한 문자를 지운다.
• 삽입(insertion): $B$의 한 문자를 $A$에 끼워 넣는다.

예를 들어 아래 그림은 $A = abcdefg$와 $B = ahcefig$의 편집 거리가 $3$임을 보여 준다. b를 h로 바꾸는 교체, d를 지우는 삭제, i를 끼워 넣는 삽입, 이렇게 세 번의 연산이 필요하다.

반복되는 문자열의 정확한 주기(exact period)는 다음과 같이 정의한다. 문자열 $x$를 $x = p^k$ ($k \ge 1$) 꼴로 쓸 수 있고 $p$가 그러한 문자열 중 가장 짧을 때, $p$를 $x$의 정확한 주기라고 한다. 예를 들어 $x = abababab$이면 $x = (abababab)^1 = (abab)^2 = (ab)^4$이므로 $ab$가 $x$의 정확한 주기이다.

근사 주기(approximate period)도 비슷하게 정의한다. 두 문자열 $x$와 $y$가 주어졌을 때, $x$를 비어 있지 않은 부분 문자열 $p_1, p_2, \dots, p_t$로 나누어 $x = p_1 \cdot p_2 \cdots p_t$로 쓴다고 하자. $y$와 모든 부분 문자열 $p_i$ 사이의 편집 거리가 정수 $k$ 이하이면, $y$를 $x$의 $k$-근사 주기라고 부른다.

$x$와 $y$가 주어질 때, $y$가 $x$의 $k$-근사 주기가 되는 최소의 $k$를 구하여라. 예를 들어 $x = abcdabcabb$이고 $y = abc$이면, $x$를 $x = p_1 \cdot p_2 \cdot p_3 = abcd \cdot abc \cdot abb$로 나눌 수 있고, $y = abc$와 abcd, abc, abb 사이의 편집 거리는 각각 $1$, $0$, $1$이다. 이 중 가장 큰 값이 $1$이므로 $y$는 $x$의 $1$-근사 주기이고, 최소의 $k$는 $1$이다.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어지며, 첫째 줄에는 문자열 $y$가, 둘째 줄에는 문자열 $x$가 주어진다. $y$의 길이는 $1 \le |y| \le 50$을, $x$의 길이는 $1 \le |x| \le 5000$을 만족하고, 두 문자열은 모두 알파벳 $\Sigma$인 소문자 영어 문자로만 이루어져 있다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 $y$가 $x$의 $k$-근사 주기가 되는 최소 정수 $k$를 한 줄에 하나씩 출력한다.