# 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| ≤ 10^{5}

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 * 10^{6}

#### Output

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

#### Samples

Input | Output |
---|---|

1 abcd bcd a | 3 |

Login to submit