Server Time: Thu Oct 1, 2020 10:54 pm
Welcome ( logout
G - Aladdin and the Magical Lamp
  PDF (English) Ranklist
Time Limit: 3 second(s) Memory Limit: 32 MB

It's said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about the seventh and final mystery.

Finally, Aladdin reached the layer of three eyed monsters, who were too dangerous. He was moving quietly without being seen. However, he was not lucky enough and some monsters found him. So, Aladdin had no option but to fight. But the monsters were too strong that Aladdin couldn't defeat them. But soon he realized that he could only beat them using some other technique. He discovered that, each eye of the three eyed monster had a rough pattern. He found the longest common sub-pattern in three eyes, and attacked the common patterns in all eyes. Surprisingly he found that the monster got weaker and weaker. And it was dead when Aladdin removed all the patterns.

And finally, Aladdin managed to kill all the monsters, and found the Lamp in a lotus. When he rubbed it, a Genie was summoned, saying, "Master, I am here, I will fulfill your three wishes". And the quest for the great magical lamp was at end, and became a history!

Here, you are given the same problem that was solved by Aladdin; that is you are given three patterns; you have to find the longest common sub-pattern in all the patterns. This sub-pattern should contain come consecutive symbols from the original patterns. For example, let the patterns be "aladdin", "adding", "dinner", then the longest sub-pattern in all the pattern is "din".

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a blank line. Each of the next three lines contains a pattern. A pattern is a non-empty string consisting of lower-case English letters whose length is no more than 5000.

Output

For each case, print the case number and the size of the longest common sub-pattern that occurs in all the patterns.

Sample Input

Output for Sample Input

2

 

aladdin

adding

dinner

 

math

magic

matters

Case 1: 3

Case 2: 2

Note

This problem was used in the Contest - Aladdin's Journey, but the max length of a string was 20.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan