Người ta đo độ giống nhau của hai xâu $X$, $Y$ có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số $i$ thỏa mãn $X_i=Y_i$. Ví dụ: $X{=}^{\prime }avb{c}^{\prime }$; $Y{=}^{\prime }avv{v}^{\prime }$ có độ giống nhau bằng $2$. Cho một xâu $S$ có độ dài $n$ và một xâu $T$ có độ dài $m(m\le n)$, độ giống nhau giữa xâu $S$ và xâu $T$ là tổng số độ giống nhau giữa xâu $T$ và mọi xâu con gồm các kí tự liên tiếp của $S$ có độ dài $m$.

Yêu cầu: Cho hai xâu $S$ và $T$. Tính độ giống nhau giữa xâu $S$ và xâu $T$.

Input

• Dòng đầu ghi xâu $T$.
• Dòng thứ $2$ ghi xâu $S$.
• Các kí tự trong hai xâu thuộc ${}^{\prime }{a}^{\prime }.{.}^{\prime }{z}^{\prime }$ và có độ dài không quá ${2.10}^6$ kí tự.

Output

• Gồm một số nguyên duy nhất là độ giống nhau giữa xâu $S$ và xâu $T$.

Subtask

• Có $25\mathrm{\%}$ số test ứng với $0<n\le {10}^2$
• Có $25\mathrm{\%}$ số test ứng với ${10}^2<n\le {10}^4$
• Có $50\mathrm{\%}$ số test ứng với ${10}^4<n\le {2.10}^6$

Sample Input 1

 abaab 
 aababacab

Sample Output 1

12