무한문자열

알파벳 소문자로만 이루어진 두 문자열 $S$, $T$가 주어진다.

문자열 $T$를 무한히 이어 붙여 만든 무한 문자열 $TTTT\dots$에 대해, $S$와 $TTTT\dots$의 LCS (Longest Common Subsequence) 의 길이를 구하여라.

LCS란, 두 문자열의 최장 공통 부분수열을 의미한다.

입력은 다음과 같은 형식으로 주어진다.

$S$ $T$

첫째 줄에 $S$와 $TTTT\dots$의 최장 공통 부분수열의 길이를 출력한다.

• $1 \leq |S| \leq 100\,000$.
• $1 \leq |T| \leq 100\,000$.
• $S$와 $T$는 알파벳 소문자로만 이루어져 있다.