Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Correcting Mistakes

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAnalyzing 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 *n* determine 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 *T* consist 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 *T* are 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".

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/18/2020 14:00:22 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|