Strings - 3

A cyclic shift of a string s is the string s_ks_k+1s_k+2 ... s_|s| s₁s₂ ... s_k-1 for some k, where |s| is the length of the string s. A substring of the string s is the string s_is_i+1 ... s_j-1s_j for some i and j. Given two strings a and b, output the number of substrings of string a which are cyclic shifts of string b.

Input

The first line of the input contains the string a (1 ≤ |a| ≤ 10⁵). The second line of the input contains the string b (1 ≤ |b| ≤ |a|). Both strings consist of letters of the English alphabet and digits only.

Output

Output one integer - the answer to the problem.

Samples

To submit solutions, register and login please.