Maximum Identical Necklace Length

Jill and Jane are sisters. Last Christmas, each of them received a string of colorful beads. Each bead color is represented by a lowercase English letter (\(a\ldots z\)), and each bead string is given as a word.

To create a necklace, each girl can remove some beads (possibly zero) from each end of her string, leaving a contiguous substring. Then, by connecting the two ends of the remaining substring, a necklace is formed. Note that a necklace is considered identical under rotation and reflection (i.e. flip).

The sisters wish their necklaces to look exactly the same, and they want the necklace to be as long as possible. What is the maximum possible length they can achieve?

inputFormat

The input consists of two lines:

• The first line contains the bead string of Jill.
• The second line contains the bead string of Jane.

Each bead string is a non-empty sequence of lowercase English letters.

outputFormat

Output a single integer representing the maximum length of a necklace that both sisters can form such that the necklaces are identical (under rotation and reflection).

sample

ab
ab

2