• # For Solution

Given 33 strings S1S1S2S2 and XX, find the number of distinct ordered pairs of strings (P,Q)(P,Q) such that :

• String P+QP+Q is a substring of XX.

• String PP is some prefix of S1S1 (possibly empty).

• String QQ is some prefix of S2S2 (possibly empty).

substring of a string is a contiguous subsequence of that string. For example, “chef” is a substring of “codechef”, but “def” is not. Also, an empty string is a substring of any string.

prefix of a string SS is a substring of SS that occurs at the beginning of SS. For example, “code” is a prefix of “codechef”, but “chef” is not. Also, an empty string is a prefix of any string.

Note: Since the input is large, prefer using fast input-output methods.

### Input Format Prefix as a Substring 2 solution codechef

• First line of the input contains TT, the number of test cases. Then the test cases follow.
• Each test case contains three lines, string S1S1 in the first line, string S2S2 in the second line and string XX in the third line. All strings consist of only lowercase Latin letters.

### Output Format Prefix as a Substring 2 solution codechef

For each test case, print a single line containing one integer denoting the number of distinct ordered pairs (P,Q)(P,Q) that satisfy the above conditions.

### Constraints Prefix as a Substring 2 solution codechef

• 1T1051≤T≤105
• 1|X|,|S1|,|S2|1061≤|X|,|S1|,|S2|≤106
• Sum of |X||X| over all test cases doesn’t exceed 106106.
• Sum of |S1||S1| over all test cases doesn’t exceed 106106.
• Sum of |S2||S2| over all test cases doesn’t exceed 106106.

### Sample Input 1  Prefix as a Substring 2 solution codechef

3
ab
bc
abc
aa
bb
ab
aab
acb
bcaabacbc


### Sample Output 1  Prefix as a Substring 2 solution codechef

7
4
11


### Explanation Prefix as a Substring 2 solution codechef

Test case 1:

There are 77 distinct ordered pairs (P,Q)(P,Q) as follows :

• PP == “” , QQ == “” (empty string)
• PP == “” , QQ == bb
• PP == “” , QQ == bcbc
• PP == aa , QQ == “”
• PP == aa , QQ == bb
• PP == aa , QQ == bcbc
• PP == abab , QQ == “”

Test case 2: Prefix as a Substring 2 solution codechef

There are 44 distinct ordered pairs as follows :

• PP == “” , QQ == “”
• PP == “” , QQ == bb
• PP == aa , QQ == “”
• PP == aa , QQ == b