Common Substrings

Time Limit: 5000MS

Memory Limit: 65536K

[显示标签]

Description

A substring of a string T is defined as:
T(i, k)=TiTi+1...Ti+k-1, 1≤ii+k-1≤|T|.
Given two strings A, B and one integer K, we define S, a set of triples (i, j, k):
S = {(i, j, k) | kK, A(i, k)=B(j, k)}.
You are to give the value of |S| for specific A, B and K.

Input

The input file contains several blocks of data. For each block, the first line contains one integer K, followed by two lines containing strings A and B, respectively. The input file is ended by K=0.1 ≤ |A|, |B| ≤ 105 1 ≤ Kmin{|A|, |B|} Characters of A and B are all Latin letters.

Output

For each case, output an integer |S|.

Sample Input

2
aababaa
abaabaa
1
xx
xx
0

Sample Output

22
5

Hint

Source

POJ Monthly--2007.10.06, wintokk

提交代码