직렬 복사는 DNA에 대한 연산으로, 하나 이상의 연속한 뉴클레오타이드로 이루어진 구간을 반복하며 반복된 구간은 서로 바로 붙어 있다. 즉, 연속한 뉴클레오타이드 구간을 복사하여 원래 구간 바로 뒤에 붙이는 연산이다. 예를 들어 $\mathrm{ATCG}$에서 $\mathrm{ATC}$를 직렬 복사하면 $\mathrm{ATCATCG}$를 얻는다. 여기에 다시 직렬 복사를 수행하면 $\mathrm{ATCATTCG}$를 얻을 수 있다. 다음 예는 $\mathrm{ATCG}$에서 시작하는 직렬 복사 연속을 보여 주며, 각 단계에서 밑줄 친 구간을 복사한다.

$$\underline{\mathrm{ATC}}\mathrm G\Rightarrow\mathrm{ATCA}\underline{\mathrm T}\mathrm{CG}\Rightarrow\underline{\mathrm{AT}}\mathrm{CATTCG}\Rightarrow\mathrm{ATATC}\underline{\mathrm{ATT}}\mathrm{CG}\Rightarrow\cdots$$

$\mathrm{ATCG}$가 직렬 복사로 이 모든 서열을 생성한다고 한다. 각 단계에서 직렬 복사할 구간을 다르게 선택하면 $\mathrm{ATCG}$에서 서로 다른 서열을 만들 수 있다는 것을 쉽게 알 수 있다. 또한 원칙적으로 직렬 복사를 필요한 만큼 계속하면 $\mathrm{ATCG}$는 무한히 많은 서열을 생성할 수 있다.

보통 더 긴 구간을 직렬 복사하는 데 더 많은 비용이 든다. 예를 들어 $\underline{\mathrm{ATC}}\mathrm G\Rightarrow\mathrm{ATCATCG}$는 뉴클레오타이드 세 개를 복사하므로 $\mathrm{ATCA}\underline{\mathrm T}\mathrm{CG}\Rightarrow\mathrm{ATCATTCG}$보다 비용이 크다. 후자는 뉴클레오타이드 하나를 복사한다. 즉, 각 단계에서 복사하는 구간의 길이가 직렬 복사 비용을 결정하는 데 중요하다.

뉴클레오타이드 하나를 직렬 복사하는 것은 쉽기 때문에, ICPC 연구실에서는 이웃한 뉴클레오타이드가 항상 서로 다른 서열을 저장하는 것이 실용적이다. 이렇게 하면 저장 공간을 줄일 수 있다. 예를 들어 $\mathrm{ATG}$에서 $\mathrm T$를 두 번 직렬 복사하여 $\mathrm{ATTTG}$를 만들 수 있으므로, $\mathrm{ATTTG}$ 대신 더 짧은 $\mathrm{ATG}$만 저장하는 것이 낫다.

최근 예산 삭감 때문에 ICPC 연구실은 한 번에 최대 두 개의 뉴클레오타이드만 직렬 복사할 수 있다. 즉, 각 단계에서 복사하는 구간의 길이는 최대 2이다. 다만 직렬 복사를 원하는 만큼 반복할 수는 있다. 예를 들어 서열 $\mathrm{ABCD}$에서 $\mathrm B$를 복사하면 $\mathrm{ABBCD}$를, $\mathrm{BC}$를 복사하면 $\mathrm{ABCBCD}$를 얻는다. 그러나 연속한 구간 $\mathrm{ABC}$는 길이가 2보다 크므로 복사할 수 없다.

원본 문자열 $s$와 목표 문자열 $t$가 주어질 때, $s$의 유효한 부분 문자열 $s\prime$의 수를 구하여라. 유효하다는 것은 $s\prime$에 적절한 횟수의 직렬 복사를 적용하여 $t$를 부분 문자열로 포함하는 문자열 $x$를 얻을 수 있다는 뜻이다. 원본 문자열에는 같은 뉴클레오타이드가 연속하지 않지만, 목표 문자열에는 연속할 수 있음에 유의하라. 예를 들어 $\mathrm{CCA}$나 $\mathrm{ATTGC}$는 원본 문자열이 될 수 없지만 목표 문자열은 될 수 있다.

이제 $s=\mathrm{ACATGCAT}$, $t=\mathrm{CCACATTT}$일 때, $s$의 부분 문자열 $s\prime=\mathrm{CATGC}$를 골라 다음과 같이 직렬 복사를 수행한다.

$$s\prime=\underline{\mathrm C}\mathrm{ATGC}\Rightarrow\mathrm C\underline{\mathrm{CA}}\mathrm{TGC}\Rightarrow\mathrm{CCACA}\underline{\mathrm T}\mathrm{GC}\Rightarrow\mathrm{CCACAT}\underline{\mathrm T}\mathrm{GC}\Rightarrow\mathrm{CCACATTTGC}$$

이 결과는 $t$를 부분 문자열로 포함한다.

다른 부분 문자열의 예를 보자. $s\prime=\mathrm{CAT}$에 대해:

$$s\prime=\underline{\mathrm{CA}}\mathrm T\Rightarrow\underline{\mathrm C}\mathrm{ACAT}\Rightarrow\mathrm{CCACA}\underline{\mathrm T}\Rightarrow\mathrm{CCACAT}\underline{\mathrm T}\Rightarrow\mathrm{CCACATTT}=t$$

이는 $\mathrm{CAT}$에서 일련의 직렬 복사로 목표 문자열을 생성할 수 있음을 보여 준다.

$s$의 유효한 부분 문자열은 총 $14$개임을 쉽게 확인할 수 있다. $s$ 안의 첫 번째 $\mathrm{CAT}$과 두 번째 $\mathrm{CAT}$은 서로 다른 유효한 부분 문자열로 센다는 점에 유의하라. 따라서 $s$의 모든 부분 문자열을 고려하고 유효한 것을 각각 세어야 한다.

다른 예로, $s=\mathrm{AB}$, $t=\mathrm{BA}$이면 부분 문자열 $\mathrm{AB}$를 골라 $\mathrm{AB}$를 직렬 복사할 수 있다. 결과 문자열은 $\mathrm{ABAB}$이며 $\mathrm{BA}$를 부분 문자열로 포함한다. $s$의 다른 모든 부분 문자열에서는 $\mathrm{BA}$를 부분 문자열로 생성할 수 없으므로 유효한 부분 문자열의 수는 1이다.

이웃한 두 문자가 같은 경우가 없는 원본 문자열 $s$와 목표 문자열 $t$가 주어진다. $s$의 유효한 부분 문자열 $s\prime$의 수를 출력하는 프로그램을 작성하여라. $s\prime$에 직렬 복사를 연속하여 수행해 $t$를 부분 문자열로 포함하는 문자열을 만들 수 있으면 $s\prime$은 유효하다. 각 단계에서는 최대 두 개의 연속한 문자만 직렬 복사할 수 있다.

입력

프로그램은 표준 입력을 읽는다. 입력은 두 줄로 이루어진다. 첫 줄은 원본 문자열 $s$이고 둘째 줄은 목표 문자열 $t$이다. 각 문자열은 대문자 A부터 Z로 이루어지며 $1\le |s|,|t|\le 2\times 10^4$이다.

출력

프로그램은 표준 출력에 정확히 한 줄을 출력해야 한다. 이 줄에는 일련의 직렬 복사로 목표 문자열을 부분 문자열로 포함하는 문자열을 만들 수 있는 유효한 부분 문자열의 수를 출력한다.

다음은 네 개의 테스트 케이스의 예제 입력과 출력이다.

예제

입력 1

ACGCG
CCG

출력 1

9

입력 2

TATCGC
TTCCG

출력 2

6

입력 3

ABCABC
ABC

출력 3

7

입력 4

ABCABC
ABCABC

출력 4

1