Another Dirty String

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.

Sample

Input	Output
1 abcd bcd a	3