줄임말

문자열 $A$가 문자열 $B$의 줄임말이라는 것은 $B$의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 $A$를 만들 수 있다는 뜻이다. 정의에 의해서 $B$는 자기 자신의 줄임말임에 유의하라. 예를 들어, ac, ab, aa, aabc는 aabc의 줄임말이고, $d, aaa, ba$는 aabc의 줄임말이 아니다.

영문 알파벳 소문자로만 이루어진 두 문자열 $S$와 $T$가 주어진다. $T$를 자연수 $n$번 반복해서 이어쓴 문자열을 $T n$이라고 하자. $S$가 $T n$의 줄임말이 되는 최소의 $n$을 구하라. 예를 들어, $T = ac, S = caa$라고 하면, $T 1 = T = ac, T 2 = acac, T 3 = acacac$이고 $n = 3$일 때 처음으로 $S$가 $T n$의 줄임말이 된다.

• $S$와 $T$는 영문 알파벳 소문자(‘$a$’ - ‘$z$’)만으로 이루어진 문자열이다.
• $S$의 길이는 1 이상 1 000 000 이하이다.
• $T$의 길이는 1 이상 100 000 이하이다.

1. (8점) $S$와 $T$는 알파벳 ‘$a$’만으로 이루어져 있다.
2. (13점) $S$의 길이와 $T$의 길이 모두 100 이하이다.
3. (21점) $S$의 길이는 10 000 이하, $T$의 길이는 100 이하이다.
4. (34점) $T$의 길이는 1 000 이하이다.
5. (24점) 추가 제약 조건이 없다.

첫째 줄에 문자열 $S$가 주어진다.

둘째 줄에 문자열 $T$가 주어진다.

$S$가 $T n$의 줄임말이 되는 최소의 $n$을 출력한다. 단, 어떤 $n$에 대해서도 $T n$이 $S$의 줄임말이 되지 못할 때에는, -1을 출력한다.