Надскладне завдання

Limits: 4 sec., 512 MiB

Богданові дали надскладне завдання — написати умову до задачі для міжнародної студентської олімпіади. Таке почесне завдання йому доручили через неабиякі навички в написанні умов. Ці навички — це результат щоденної роботи над умовами.

Богдан знає, що для того щоб написати гарні умови потрібно лише трохи змінити минулорічні. Минулого року він вже писав дві такі умови. Ці умови можна записати як два рядки — \(s\) та \(t\). Богдан впевнений, що для того щоб написати гарну умову потрібно знати скільки однакових пар підрядків є в рядках \(s\) та \(t\). Звісно він міг би сам знайти це, але йому ж ніколи — олімпіада вже на носі. Допоможіть йому знайти скільки однакових пар підрядків є в рядках \(s\) та \(t\). Тобто, потрібно знайти кількість четвірок \(l_1\), \(r_1\), \(l_2\), \(r_2\), таких що \(r_1 - l_1 = r_2 - l_2\) і \(s[l_1 ... r_1] = t[l_2 ... r_2]\).

Підрядок — це непорожня зв’язна частина рядка. Тобто такий рядок, який можна отримати за допомогою видалення будь-якої кількості символів з початку та з кінця рядка.

Input

У першому рядку задано один рядок \(s\).

У другому рядку задано один рядок \(t\).

Output

В єдиному рядку виведіть кількість однакових підрядків рядків \(s\) та \(t\).

Constraints

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

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

\(|s|\) — позначає довжину рядка,

рядки складаються лише із маленьких букв англійського алфавіту (a-z).

Оцінювання задачі складається із наступних блоків:

1 бал — приклад з умови,

4 бали — блок тестів у яких \(|s| \le 50\) і \(|t| \le 50\),

10 балів — блок тестів у яких \(|s| \le 300\) і \(|t| \le 300\),

10 балів — блок тестів у яких \(|s| \le 10^4\) і \(|t| \le 300\),

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Samples

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

Notes

В першому прикладі є одна спільна пара підрядків ab, одна пара підрядків b та 4 пари підрядків a.