Very Dirty String

IamHot 1st LU National ICT Fest...
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 .

Sample

InputOutput
1
AB
AB
A
Case 1: 2

Submit

Login to submit.

Statistics

53% Solution Ratio
lexuananEarliest, Aug '17
Eleus_AhammadFastest, 0.0s
lexuananLightest, 262 kB
SIR.24Shortest, 830B
Toph uses cookies. By continuing you agree to our Cookie Policy.