Given two strings �1T1 and �2T2, a string �X is �T-nested if and only if �X can be represented as the string obtained by inserting �2T2 at a position in �1T1. For example, if �1=abcdT1=abcd and �2=efT2=ef, then efabcdefabcd, aefbcdaefbcd and abcdefabcdef are all �T-nested strings.
Given strings �S, �1T1, and �2T2, 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 �2T2 in �1T1 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≤�≤201≤T≤20), denoting the number of test cases.
The first line of each test case contains two strings �1T1 and �2T2 (∣�1∣+∣�2∣≤∣�∣∣T1∣+∣T2∣≤∣S∣) separated by a single space.
The second line of each test case contains a single string �S (∣�∣≤107∣S∣≤107).
It is guaranteed that �S, �1T1, and �2T2 all consist only of lowercase letters and ∑∣�∣≤2×107∑∣S∣≤2×107. Here, ∣�∣∣S∣ means the length of string �S.
3
abab ab
abababab
ab a
aaabbaabaa
aba ab
ababaabbabaab6
5
5