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 an end, and became 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 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.

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