Correcting Mistakes

 CodeForces - 533E 

Analyzing the mistakes people make while typing search queries is a complex and an interesting work. As there is no guaranteed way to determine what the user originally meant by typing some query, we have to use different sorts of heuristics.

Polycarp needed to write a code that could, given two words, check whether they could have been obtained from the same word as a result of typos. Polycarpus suggested that the most common typo is skipping exactly one letter as you type a word.

Implement a program that can, given two distinct words S and T of the same length ndetermine how many words W of length n + 1 are there with such property that you can transform W into both S, and T by deleting exactly one character. Words S and Tconsist of lowercase English letters. Word W also should consist of lowercase English letters.

Input

The first line contains integer n (1 ≤ n ≤ 100 000) — the length of words S and T.

The second line contains word S.

The third line contains word T.

Words S and T consist of lowercase English letters. It is guaranteed that S and Tare distinct words.

Output

Print a single integer — the number of distinct words W that can be transformed to S and T due to a typo.

Examples

Input

7
reading
trading

Output

1

Input

5
sweet
sheep

Output

0

Input

3
toy
try

Output

2

Note

In the first sample test the two given words could be obtained only from word "treading" (the deleted letters are marked in bold).

In the second sample test the two given words couldn't be obtained from the same word by removing one letter.

In the third sample test the two given words could be obtained from either word "tory" or word "troy".

 

题目大意：给你两个字符串，这两个串都是在原串的基础上减去一个字母得到的，问你原串有几种可能性。

sol：首先把首尾两端相等的去掉，容易发现答案最大是2,

一开始睿智了，写了个XJB玩意，只判了两个位置，就会被这样的卡掉

如

aaab

baaa

于是就爆枚两种情况，一是S1的[L,R-1]等于S2的[L+1,R]，还有一种就是类比一下

/*
题目大意：给你两个字符串，这两个串都是在原串的基础上减去一个字母得到的，问你原串有几种可能性。
*/
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0; bool f=0; char ch=' ';
    while(!isdigit(ch))    {f|=(ch=='-'); ch=getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0) {putchar('-'); x=-x;}
    if(x<10) {putchar(x+'0'); return;}
    write(x/10); putchar((x%10)+'0');
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=100005;
int n,p[N],ans=0,l,r,len;
char S[2][N];
inline void Jud(int o)
{
    int i;
    for(i=l;i<r;i++)
    {
        if(S[o][i]!=S[o^1][i+1]) return;
    }
    ans++;
}
int main()
{
    int i;
    R(n);
    scanf("%s%s",S[0]+1,S[1]+1);
    l=1; r=n;
    while(S[0][l]==S[1][l]) l++;
    while(S[0][r]==S[1][r]) r--;
    if(l==n+1&&r==0)
    {
        Wl((n+1)*26); return 0;
    }
//    cout<<l<<" "<<r<<endl;
    len=r-l+1;
    Jud(0);
    Jud(1);
    Wl(ans);
    return 0;
}
/*
input
4
aaab
baaa
output
1 
*/

View Code