After the recent apocalypse, Azamat, nally, learned about the largest common subsequences of two strings and now he is interested, what will be the largest common subsequence of two round words?

In a round word there is no dierence from which symbol the word starts and in which direction it is read. For instance, the round word algorithm can be read as rithmalgo and as oglamhtir.

For usual words algorithm and grammar the longest common subsequence length is 3 (the word grm), and for round variant of the same word the length of the longest common subsequence is 4 (the word grma).

Azamat quickly found out that the standard algorithm cannot get right answer for round words. Write the program which will do that for him.

Input

Two lines contain one word each. Words are non-empty and the length of each words doesn't exceed 2000 characters.

Output

The single line must contain one integer number - the length of the longest common subsequence of the given round words.