All submissions for this problem are available.You are given three strings $A, B, C$. You want to find a string $Z$ (possibly empty) such that the string $A + Z + B$ contains $C$ as a substring. Find out the smallest possible length of string $A + Z + B$ that can satisfy the above criteria. ### Input - The first line of the input contains an integer $T$ denoting the number of test cases. The description of the test cases follows. - Each testcase consists of three lines which contain the strings $A, B, C$ respectively. ### Output For each test case, output an integer corresponding to the answer of the problem. ###Constraints - $1 \le T \le 10^5$ - $1 \le |A|, |B|, |C| \leq 2 * 10^5$ - Each string consists only of lower case English alphabets ('a' to 'z') - Sum of the length of all three strings over all the testcases doesn't exceed $6 * 10^6$ ### Example Input ``` 2 abc cde bccd abc cde cec ``` ### Example Output ``` 6 7 ``` ###Explanation: **Testcase 1**: Take $Z$ to be the empty string. So now, $A + Z + B$ becomes "abccde", and "bccd" is a substring of it. So this is a valid choice, and you can see that you cannot get a shorter string. Hence the answer is 6. **Testcase 2**: Take $Z$ = "e". So now, $A + Z + B$ becomes "abcecde", and "cec" is a substring of it. So this is a valid choice, and you can see that you cannot get a shorter string. Hence the answer is 7.
|Time Limit:||1.75 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, kotlin|
Fetching successful submissions