Nested String

Problem Description

Given two strings $T_1$ and $T_2$, a string $X$ is $T$-nested if and only if $X$ can be represented as the string obtained by inserting $T_2$ at a position in $T_1$. For example, if $T_1=\texttt{abcd}$ and $T_2=\texttt{ef}$, then $\texttt{efabcd}$, $\texttt{aefbcd}$ and $\texttt{abcdef}$ are all $T$-nested strings. Given strings $S$, $T_1$, and $T_2$, your task is to compute the count of distinct $T$-nested substrings in $S$. Two nested substrings are considered distinct if they either occur at different positions in $S$, or the insert positions of $T_2$ in $T_1$ are different . A substring of $S$ means a continuous sequence of characters from string $S$.

Input

Ensure to use cin/cout and disable synchronization with stdio to avoid unexpected TLE verdict. The first line contains a single integer $T$ ($1\le T\le 20$), denoting the number of test cases. The first line of each test case contains two strings $T_1$ and $T_2$ ($|T_1|+|T_2|\le |S|$) separated by a single space. The second line of each test case contains a single string $S$ ($|S|\le 10^7$). It is guaranteed that $S$, $T_1$, and $T_2$ all consist only of lowercase letters and $\sum |S|\le 2\times 10^7$. Here, $|S|$ means the length of string $S$.

Output

For each test case, output an integer in a single line representing the number of distinct $T$-nested substrings in $S$.

Sample Input

3
abab ab
abababab
ab a
aaabbaabaa
aba ab
ababaabbabaab

Sample Output

6
5
5

Hint

In the first test case, the $6$ $T$-nested substrings are (the substring is underlined and the part from $T_2$ is highlighted in bold): $\underline{\textbf{ab}\text{abab}}\text{ab}$ $\underline{\text{ab}\textbf{ab}\text{ab}}\text{ab}$ $\underline{\text{abab}\textbf{ab}}\text{ab}$ $\text{ab}\underline{\textbf{ab}\text{abab}}$ $\text{ab}\underline{\text{ab}\textbf{ab}\text{ab}}$ $\text{ab}\underline{\text{abab}\textbf{ab}}$

Source

2023“钉耙编程”中国大学生算法设计超级联赛（8）