タンデムコピーとは、DNA 上で 1 個以上の連続したヌクレオチドの列を繰り返し、その繰り返しを互いに隣接させる操作です。つまり、連続したヌクレオチドの列を複製し、そのコピーを元の列の直後に貼り付けます。例えば $\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}$ から異なる列を生成できることは容易に分かります。また原理的には、必要なだけタンデムコピーを続けることで、無限に多くの列を生成できます。

通常、長い部分をタンデムコピーするほど高い費用がかかります。例えば $\underline{\mathrm{ATC}}\mathrm G\Rightarrow\mathrm{ATCATCG}$ は 3 個のヌクレオチドのコピーであり、$\mathrm{ATCA}\underline{\mathrm T}\mathrm{CG}\Rightarrow\mathrm{ATCATTCG}$ より高価です。後者は 1 個のヌクレオチドのコピーです。つまり、各段階でコピーする部分の長さが費用を決めるうえで重要です。

1 個のヌクレオチドをタンデムコピーするのは簡単なので、ICPC 研究室では隣接するヌクレオチドが常に異なる列を保存するのが実用的です。これにより保存容量を減らせます。例えば $\mathrm{ATG}$ から $\mathrm T$ を 2 回コピーすれば $\mathrm{ATTTG}$ を作れるので、$\mathrm{ATTTG}$ の代わりに短い $\mathrm{ATG}$ だけを保存する方がよいのです。

最近の予算削減により、ICPC 研究室は一度に高々 2 個のヌクレオチドしかタンデムコピーできません。つまり、各段階でコピーする部分の長さは高々 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}$ と 2 つ目の $\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$ を部分文字列として含む文字列を生成できれば有効です。各段階では高々 2 個の連続する文字しかコピーできません。

入力

プログラムは標準入力から読み取ります。入力は 2 行からなり、最初は元文字列 $s$、2 行目は目標文字列 $t$ です。各文字列は大文字 A から Z からなり、$1\le |s|,|t|\le 2\times 10^4$ です。

出力

プログラムは標準出力にちょうど 1 行を出力してください。その行には、一連のタンデムコピーで目標文字列を部分文字列として含む文字列を生成できる、有効な部分文字列の数を出力してください。

以下に 4 つのテストケースの入力例と出力例を示します。

入出力例

入力 1

ACGCG
CCG

出力 1

9

入力 2

TATCGC
TTCCG

出力 2

6

入力 3

ABCABC
ABC

出力 3

7

入力 4

ABCABC
ABCABC

出力 4

1