Bomb Disposal Strings

Prohor is the cheif of bomb disposal unit of "Anti Terrorists Squad" (ATTS). She is now in PeculiarLand where thousands of innocent people die in bomb blast. There are two bombs and she wants to dispose them to save people.

There is a string (of lowercase Latin letters) written on each bomb.
Two bombs can be deactivated only by entering the correct password.

This information is leaked by her friend Sabiha, who is a journalist.

The password can be found by concatenating those two strings in such a way it produces the minimum length, abiding by some rules.

Let's say, one of the strings is string1 and another one is string2 .

Rule1:

1. First Prohor has to find the longest prefix of string2 that occurs in string2 one more time as a substring. That means, the frequency of the prefix in string2 has to be at least 2, and Prohor must choose the longest such prefix.

2. Then Prohor has to check if that longest prefix of string2 also exists in string1. If it does, then Prohor removes that prefix from string2 and then concatenates string2 at the end of string1.
   If the longest prefix of string2 doesn't exist in string1, Prohor has to concatenate whole string2 at the end of string1.

Let,
string2 = "abcabcdbbb", string1 = "sabc".

We see, "abc" is the longest prefix of string2 which is twice there and it is present in string1 too (once).

So we get "sabc"+"abcdbbb" = "sabcabcdbbb". (Note that "abc" from string2 is left out )

Rule 2:
If rule 1 doesn't apply, the entire string2 will be added at the end of string1.

After all these concatenations, we can get the final_string , which must be of the minimum length among all possible concatenations strictly abiding by the rules.

If there are multiple concatenations with minimum length, the final_string will be the lexicographically smaller one.

The password is the number of palindromic substring in final_string.

Prohor knows this task requires some programming and she's not so good at it. Now she asks for your help.

Input

There will be two strings, a and b respectively ( a and b can have no more than 1000000 characters and will be non-empty )

Output

Print the correct password.

Samples

Input	Output
abc def	6

Input	Output
abcpqrs pqrspqrst	12

1. Palindromes can overlap. i.e. final_string = "bbb" . There are 6 palindromes : b, b, b, bb, bb and bbb.

2. Longest prefix in bbb that occurs at least twice is bb. Frequency of bb is 2 in the string. But frequency of bbb is 1, so it can't be the longest prefix satisfying the condition