题目描述

字符串 T 的子串定义为：
T(i, k) = T_i T_{i+1} … T_{i+k-1}，其中 1 ≤ i ≤ i+k-1 ≤ |T|（|T| 表示 T 的长度）。
给定两个字符串 A、B 和整数 K，定义集合 S 为满足以下条件的三元组 (i, j, k) 的集合：
S = {(i, j, k) | k ≥ K，且 A(i, k) = B(j, k)}。
求集合 S 的元素个数 |S|。

输入

输入包含多组数据。每组数据的第一行是整数 K，接下来两行分别是字符串 A 和 B。当 K=0 时输入结束。

• 1 ≤ |A|, |B| ≤ 10^5
• 1 ≤ K ≤ min(|A|, |B|)
• 字符串 A 和 B 仅包含拉丁字母。

输出

对每组数据，输出 |S| 的值。

输入示例 1

2  
aababaa  
abaabaa  
1  
xx  
xx  
0  

输出示例 1

22  
5  

题目来源

POJ Monthly--2007.10.06, wintokk