1 const maxn=200419;  2 var  3  c,h,rank,sa,x,y,stack:array[0..maxn] of longint;  4  n,k,top:longint;  5  a,b,d:int64;  6  s1,s2:ansistring;  7   8 function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end;  9 function min(x,y:longint):longint; begin if x<y then exit(x) else exit(y); end; 10  11 procedure make; 12 var p,i,tot:longint; 13 begin 14  p:=1; 15  while p<n do 16   begin 17    fillchar(c,sizeof(c),0); 18    for i:= 1 to n-p do y[i]:=rank[i+p]; 19    for i:= n-p+1 to n do y[i]:=0; 20    for i:= 1 to n do inc(c[y[i]]); 21    for i:= 1 to n do inc(c[i],c[i-1]); 22    for i:= 1 to n do 23     begin 24      sa[c[y[i]]]:=i; 25      dec(c[y[i]]); 26     end; 27    fillchar(c,sizeof(c),0); 28    for i:= 1 to n do x[i]:=rank[i]; 29    for i:= 1 to n do inc(c[x[i]]); 30    for i:= 1 to n do inc(c[i],c[i-1]); 31    for i:= n downto 1 do 32     begin 33      y[sa[i]]:=c[x[sa[i]]]; 34      dec(c[x[sa[i]]]); 35     end; 36    for i:= 1 to n do sa[y[i]]:=i; 37    tot:=1; 38    rank[sa[1]]:=1; 39    for i:= 2 to n do 40     begin 41      if (x[sa[i]]<>x[sa[i-1]]) or (x[sa[i]+p]<>x[sa[i-1]+p]) then inc(tot); 42      rank[sa[i]]:=tot; 43     end; 44    p:=p<<1; 45   end; 46  for i:= 1 to n do sa[rank[i]]:=i; 47 end; 48  49 procedure makeh(s:ansistring); 50 var i,j,p:longint; 51 begin 52  h[1]:=0; p:=0; 53  for i:= 1 to n do 54   begin 55    p:=max(p-1,0); 56    if rank[i]=1 then continue; 57    j:=sa[rank[i]-1]; 58    while (i+p<=n) and (j+p<=n) and (s[i+p]=s[j+p]) do inc(p); 59    h[rank[i]]:=p; 60   end; 61 end; 62  63 procedure init(s:ansistring); 64 var i,tot:longint; 65  ch:char; 66 begin 67  n:=length(s); 68  for i:= 1 to n do c[i]:=0; 69  for i:= 1 to n do x[i]:=ord(s[i]); 70  for i:= 1 to n do inc(c[x[i]]); 71  for i:= 1 to 122 do inc(c[i],c[i-1]); 72  for i:= 1 to n do 73   begin 74    sa[c[x[i]]]:=i; 75    dec(c[x[i]]); 76   end; 77  rank[sa[1]]:=1; 78  tot:=1; 79  for i:= 2 to n do 80   begin 81    if x[sa[i]]<>x[sa[i-1]] then inc(tot); 82    rank[sa[i]]:=tot; 83   end; 84  fillchar(x,sizeof(x),0); 85  fillchar(y,sizeof(y),0); 86  make; 87  makeh(s); 88 end; 89  90 function calc(s:ansistring):int64; 91 var ctb,i,m,ht,top:longint; 92  ans:int64; 93 begin 94  ans:=0; 95  init(s); 96  h[0]:=k-1; h[n+1]:=k-1; 97  top:=0; i:=1; 98  stack[0]:=0; 99  while i<=n+1 do100   begin101    ht:=h[stack[top]];102    if ((h[i]<k) and (top=0)) or (h[i]=ht) then inc(i)103     else if h[i]>ht then begin inc(top);stack[top]:=i; inc(i); end104      else105       begin106        m:=i-stack[top]+1;107        if (h[i]>=k) and (h[i]>h[stack[top-1]]) then108         begin109          ctb:=ht-h[i];110          h[stack[top]]:=h[i];111         end112        else113         begin114          ctb:=ht-h[stack[top-1]];115          dec(top);116         end;117        inc(ans,(int64(m)*int64(m-1) div 2) *int64(ctb));118       end119   end;120  exit(ans);121 end;122 123 Begin124  readln(k);125  while k<>0 do126   begin127    readln(s1);128    a:=calc(s1);129    readln(s2);130    b:=calc(s2);131    s1:=s1+‘$‘+s2;132    d:=calc(s1);133    writeln(d-a-b);134    readln(k);135   end;136 End.