串联复制（tandem copy）是 DNA 上的一种操作，即将一段连续的核苷酸序列重复，且重复部分紧邻原序列；换句话说，串联复制操作会复制一段连续的核苷酸序列，并将其粘贴在原序列之后。例如，我们可以对 ATCG 进行串联复制 ATC，得到 ATCATCG。此外，我们还可以对结果序列 ATCATCG 进行另一次串联复制操作，得到 ATCATTCG。以下示例展示了从 ATCG 开始的一系列串联复制，其中下划线序列为每一步复制的内容：

ATCG $\Rightarrow$ ATCATCG $\Rightarrow$ ATCATTCG $\Rightarrow$ ATATCATTCG $\Rightarrow$ $\dots$

我们称 ATCG 通过串联复制产生了所有这些序列。显而易见，通过在每一步选择序列的不同部分进行操作，ATCG 可以产生不同的序列。此外，原则上 ATCG 通过进行不同的操作可以产生无穷多种序列。通常，串联复制序列中较长的部分代价更高。例如，

ATCG $\Rightarrow$ ATCATCG

是对三个核苷酸进行的串联复制，因此比

ATCATCG $\Rightarrow$ ATCATTCG

（这是对一个核苷酸进行的串联复制）代价更高。换句话说，每一步复制部分的长度对于确定串联复制的代价至关重要。

由于对单个核苷酸进行串联复制很容易，基因工程实验室通常会存储这样的序列：序列中任意两个相邻的核苷酸总是不同的；这有助于实验室减少存储空间。例如，由于 ATTTG 可以通过对 ATG 中的 T 进行两次串联复制产生，实验室最好只存储较短的序列 ATG 而不是 ATTTG。

由于最近预算削减，实验室一次只能对最多两个核苷酸进行串联复制。换句话说，每一步复制部分的长度最多为二。另一方面，实验室可以根据需要进行任意多次串联复制操作。例如，给定序列 ACGT，我们可以对 C 进行串联复制得到 ACCGT，或者对序列 CG 进行串联复制得到 ACGCGT。但我们不能对连续序列 ACG 进行串联复制，因为它的长度超过了二。

给定源字符串 $s$ 和目标字符串 $t$，你的任务是计算 $s$ 的有效子串数量。如果一个子串 $s'$ 可以通过应用适当次数的串联复制操作得到一个字符串 $x$，且 $x$ 包含 $t$ 作为其子串，则称该子串 $s'$ 是有效的。请注意，源字符串中没有两个连续的核苷酸是相同的，而目标字符串中两个连续的核苷酸可以是相同的。例如，CCA 或 ATTGC 不能作为源字符串，但它们可以作为目标字符串。

现在，给定 $s = \text{ACATGCAT}$ 和 $t = \text{CCACATTT}$，我们取 $s$ 的子串 $s' = \text{CATGC}$ 并进行一系列串联复制如下：

$s' = \text{CATGC} \Rightarrow \text{CCATGC} \Rightarrow \text{CCACATGC} \Rightarrow \text{CCACATTGC} \Rightarrow \text{CCACATTTGC}$

该结果包含 $t$ 作为其子串。

这是另一个子串示例。对于 $s' = \text{CAT}$：

$s' = \text{CAT} \Rightarrow \text{CACAT} \Rightarrow \text{CCACAT} \Rightarrow \text{CCACATT} \Rightarrow \text{CCACATTT} = t$

这表明我们可以通过一系列串联复制从 CAT 产生目标字符串。

很容易验证 $s$ 的有效子串总数为 14。注意，$s$ 中的第一个和第二个 CAT 都被视为不同的有效子串。因此，你需要将字符串 $s$ 的所有部分视为子串，并分别计算所有有效子串。

这是另一个示例。 当 $s = \text{AC}$ 且 $t = \text{CA}$ 时，你可以取子串 AC 并对 AC 进行串联复制。然后，得到的字符串是 ACAC，它包含 CA 作为其子串。$s$ 的所有其他子串都无法产生 CA 作为子串，因此有效子串的数量为一。

给定源字符串 $s$ 和目标字符串 $t$，其中 $s$ 中没有两个连续字符相同，编写一个程序输出 $s$ 的有效子串 $s'$ 的数量。

输入格式

输入包含两行。第一行是源字符串 $s$，第二行是目标字符串 $t$。每个输入均由大写英文字母组成，且 $1 \le |s|, |t| \le 2 \cdot 10^4$。保证 $s$ 中没有两个连续字符相同。

输出格式

打印恰好一行。该行应包含有效子串的数量。

样例

样例输入 1

ATGTG
TTG

样例输出 1

9

样例输入 2

CACTGT
CCTTG

样例输出 2

6

样例输入 3

PQRPQR
PQR

样例输出 3

7

样例输入 4

BCDBCD
BCDBCD

样例输出 4

1