Migrated from Lutece 606 Palindrome Again

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Palindrome really has many many properties which fascinated us a lot and arouse many interests.

Do you remember that last summer, the problem about longest palindrome in the inteval?

Too easy? Maybe you are tired of solving problem about palindrome on one string.

Here is your another challenge.

There are two strings, $A$ and $B$, and an integer $d$.

And you are to count the number of triples $(i,j,k)$. that satisfies $A.substr(i,k)=B.substr(j,k)$, $1\leq i\leq strlen(A)$, $1\leq j\leq strlen(B)$, $A.substr(i,k)$ is a palindrome, $k$ is the length of the substring, $k\geq d$

A substring of a string $T$ is defined as:

$T.substr(i, k)=T_iT_{i+1}\cdots T_{i+k-1}$, $1\leq i\leq i+k-1\leq |T|$.

Input

The input file contains several cases, end by EOF. For each cases, the first line contains one integer $d$, followed by two lines containing strings $A$ and $B$, respectively.

$1 \leq strlen(A), strlen(B) \leq 50000$

$1 \leq d \leq min\{strlen(A), strlen(B)\}$

Characters of $A$ and $B$ are all lowercase letters.

Output

For each case, output an integer indicates the number of the triples $(i,j,k)$.

Samples

1
aba
aba
1
icpc
cicpc
2
myon
usagi

6
9
0

Note

In the first sample , the $6$ triples are

$1,1,1$

$1,3,1$

$2,2,1$

$3,1,1$

$3,3,1$

$1,1,3$

respectively.

Resources

6th BUPT Programming Contest Final