Giải bài trực tuyến

Two operations on one string

John is given a string S. He is asked to do the following two operations in the given order to S:

1. Choose one element of S, and replace it with any character he wants.
2. Shift the string S, that means, he may choose a position k and shifts the whole string circularly so that k becomes be the first place of the new string.

John wants the result to be a specified string. It's up to you to tell him how many ways to transform S to a given string T.

Input

• The input consists of two strings S and T in a line. Each string contains at most 100000 characters. Only capital letters will occur in the strings.
• It is guaranteed that S and T have the same length.

Output

Only one number, the number of ways to transform S to T.

Example

Input
AHYANGYI YANGYIAH

Output
8

Output details
John can replace the first "A" with "A", or "H" with "H", etc. 
i.e. it is allowed to replace a chatacter with itself.
After that, there's one way to shift the string.

Input
VSUMSU MSUMSU

Output
2

Output details
John should replace the first "V" with "M". 
After that, he has two ways to shift the string (k=1 or k=4).