A. abc - 变换
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定两个仅由字符 $$$\{\texttt{a}, \texttt{b}, \texttt{c}\}$$$ 组成的字符串 $$$S$$$ 和 $$$T$$$。你可以对字符串 $$$S$$$ 进行任意次（包括零次）以下操作：

  • 选择 $$$S$$$ 中的一个字符 a，将其替换为 bc；
  • 选择 $$$S$$$ 中的一个字符 b，将其替换为 ca；
  • 选择 $$$S$$$ 中的一个字符 c，将其替换为 ab；
  • 选择 $$$S$$$ 中相邻的两个相同字符，将它们一并删除。

现在，你需要回答在字符串 $$$T$$$ 中，有多少个不同的子串能够由初始串 $$$S$$$ 经过有限次上述操作后得到。

这里，字符串 $$$T$$$ 的子串定义为 $$$T$$$ 中连续的一段字符序列，即对于下标 $$$l, r$$$ $$$(1 \le l \le r \le |T|)$$$，子串表示为 $$$T_l T_{l+1} \dots T_r$$$。需要注意的是，两个子串被认为是不同的，当且仅当它们在 $$$T$$$ 中对应的下标区间不同；即使两个子串的字符序列完全相同，只要它们的位置不同，就会被视作不同的子串。

Input

第一行输入一个整数 $$$t$$$ $$$(1 \le t \le 10^5)$$$，表示测试数据组数。

接下来 $$$2t$$$ 行，每两组数据包含以下两行：

  • 第一行输入一个字符串 $$$S$$$。
  • 第二行输入一个字符串 $$$T$$$。

保证所有字符串均只由小写字母 a、b、c 构成。保证所有测试数据中，$$$\sum |S| \le 2 \times 10^6$$$ 且 $$$\sum |T| \le 2 \times 10^6$$$。

Output

对于每组测试数据，输出一行一个整数，表示 $$$T$$$ 中能够由 $$$S$$$ 经过操作得到的子串的个数。

Example
Input
1
a
aabc
Output
4
Note

对于唯一的测试数据，初始串 $$$S = \texttt{"a"}$$$：

  • 不进行任何操作，可得到串 "a"，它对应 $$$T$$$ 中两个不同位置的子串：$$$T[1,1] = \texttt{"a"}$$$ 和 $$$T[2,2] = \texttt{"a"}$$$；
  • 对唯一的 "a" 执行一次替换为 "bc" 的操作，得到串 "bc"，它对应 $$$T[3,4] = \texttt{"bc"}$$$；
  • 在上一步得到 "bc" 后，可继续操作（具体操作序列略），最终可得到串 "aabc"，对应 $$$T[1,4] = \texttt{"aabc"}$$$。

因此符合条件的子串共 $$$4$$$ 个：$$$T[1,1]$$$、$$$T[2,2]$$$、$$$T[3,4]$$$、$$$T[1,4]$$$。