Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Another Dirty String

Limits: 1s, 1.0 GB

Given three strings A, B and C.

Find the length of the longest common substring of A and B, which doesn’t have C as a substring.

Input

There will be T test cases.

For each test there will be three lines describing string A, B, and C.

1 ≤ T ≤ 100

1 ≤ |A|, |B|, |C| ≤ 105

Note : |S| defines the length of string S.

A, B and C will contain only upper and lower case characters and no white-space.

And the summation of all strings over all test cases wouldn’t be over 3 * 106

Output

For each test case output just one line representing the ans of the test case.

Samples

InputOutput
1
abcd
bcd
a
3

Discussion
Submit

Login to submit