Super-difficult problem

Limits: 4 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Bogdan was given a super-difficult task — to write a problem statement for the international collegiate programming contest. Such an honorable task was entrusted to him due to his remarkable skills in writing problem statements. These skills are the result of daily work on statements.

Bogdan knows that in order to write good statements, one only needs to slightly modify last year’s ones. Last year he already wrote two such statements. These statements can be written as two strings — \(s\) and \(t\). Bogdan is sure that in order to write a good statement, one needs to know how many identical pairs of substrings there are in strings \(s\) and \(t\). Of course he could find this himself, but he has no time — the contest is approaching fast. Help him find how many identical pairs of substrings there are in strings \(s\) and \(t\). That is, you need to find the number of quadruples \(l_1\), \(r_1\), \(l_2\), \(r_2\), such that \(r_1 - l_1 = r_2 - l_2\) and \(s[l_1 ... r_1] = t[l_2 ... r_2]\).

A substring is a non-empty contiguous part of a string. That is, a string that can be obtained by deleting any number of characters from the beginning and the end of the string.

Input

The first line gives a single string \(s\).

The second line gives a single string \(t\).

Output

In a single line, output the number of identical pairs of substrings of strings \(s\) and \(t\).

Constraints

\(1 \le |s| \le 10^4\),

\(1 \le |t| \le 300\),

\(|s|\) — denotes the length of the string,

the strings consist only of lowercase English letters (a-z).

Problem evaluation consists of the following subtasks:

1 point — example from the statement,

4 points — a block of tests in which \(|s| \le 50\) and \(|t| \le 50\),

10 points — a block of tests in which \(|s| \le 300\) and \(|t| \le 300\),

10 points — a block of tests in which \(|s| \le 10^4\) and \(|t| \le 300\),

You will receive the points for a subtask only if you give the correct answer to all tests in the subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
aba aab	6

Notes

In the first example, there is one common pair of substrings ab, one pair of substrings b, and 4 pairs of substrings a.