问题 F: Nested String

Given two strings T1 and T2, a string X is T-nested if and only if X can be represented as the string obtained by inserting T2 at a position in T1. For example, if T1 = abcd and T2 = ef, then efabcd, aefbcd and abcdef are all T-nested strings. Given strings S, T1, and T2, 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 T2 in T1 are different. A substring of S means a continuous sequence of characters from string S. 

Ensure to use cin/cout and disable synchronization with stdio to avoid unexpected TLE verdict. The first line contains a single integer T (1 ≤ T ≤ 20), denoting the number of test cases. The first line of each test case contains two strings T1 and T2 (|T1| + |T2| ≤ |S|) separated by a single space. The second line of each test case contains a single string S (|S| ≤ 107 ). It is guaranteed that S, T1, and T2 all consist only of lowercase letters and P|S| ≤ 2 × 107 . Here, |S| means the length of string S.

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

3
abab ab
abababab
ab a
aaabbaabaa
aba ab
ababaabbabaab

6
5
5

In the first test case, the 6 T-nested substrings are (the substring is underlined and the part from T2 is highlighted in bold):
 1. abababab 2. abababab 3. abababab 4. abababab 5. abababab 6. abababab