Practice on Toph

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

Very Dirty String

Limits: 1s, 512 MB

Strings are difficult, most of the contest programmers say this and try to avoid string algorithms. But actually strings are fun and not that difficult. It’s just that we don’t try hard enough and haven’t grown that confidence in ourselves. And there are many very good problems which you may think need difficult string algorithms to solve but actually they are very easy and straightforward if you know some simple tricks.

Now, you will be given a string related problem. Can you solve this and prove that strings aren’t that difficult :D.

Given three strings A, B and C.

Find the longest common sub-sequence of A and B, which have C at-least once as a substring in it.

Input

There will be T (1 ≤ T ≤ 100) test cases.

For each test there will be three lines describing string A, B, and C (1 ≤ |A|, |B|, |C| ≤ 100). |S| defines the length of string S.

Note: Do not use gets() or getline() functions. normal scanf() or cin is good enough.

Output

For each test case output one lines. First the case number then the length of the longest such string .

Samples

InputOutput
1
AB
AB
A
Case 1: 2

Author
Discussion
Submit

Login to submit