# B :: Bracelets

Time Limit: 30 Seconds Memory Limit: 65536 KB

Finally, Megamind has devised the perfect plan to take down his arch-nemesis, Metro Man! Mega-mind has designed a pair of circular power bracelets to be worn on his left and right wrists. On each bracelet, he has inscribed a sequence of magical glyphs (i.e., symbols); each activated glyph augments Megamind’s strength by the might of one grizzly bear!

However, there’s a catch: the bracelets only work when the subsequences of glyphs activated on each bracelet are identical. For example, given a pair of bracelets whose glyphs are represented by the strings “metrocity” and “kryptonite”, then the optimal activation of glyphs would give Megamind the power of 10 grizzly bears:

## Input

The input file will contain at most 100 test cases (including at most 5 “large” test cases). Each test case is given by a single line containing a space-separated pair of strings s and t, corresponding to the sequences of glyphs on Megamind’s left and right power bracelets, respectively. Each string will consist of only lowercase letters (‘a’-‘z’). The length of each input string will be between 1 and 100 characters, inclusive, except for the large test cases where the length of each input string will be between 1 and 1500 characters, inclusive.

## Output

For each input test case, print the maximum power (in units of grizzly bears) that Megamind will be able to achieve by activating glyphs on his bracelets.

## Sample Input

metrocity kryptonite megamind agemdnim metroman manmetro megamindandmetroman metromanandmegamind

## Sample Output

10 16 16 32Submit

Source: 2011 Pacific Northwest Region Programming Contest