Given a $2 \times n$ grid, the top-left cell is labeled $(1, 1)$ and the bottom-right cell is $(2, n)$. Each cell contains a character (lowercase English letter). You can start at any cell, move only right or down at each step, and stop at any cell. It is easy to see that any such path is a simple path (i.e., it visits each cell at most once).

A path is called a palindrome path if the string formed by the characters of the path in the order they are visited is a palindrome. The length of a path is defined as the number of cells visited. You need to find the length of the longest palindrome path.

Input

The first line contains a positive integer $n$.

The next two lines each contain a string of length $n$. The $i$-th character of the first line represents the character in cell $(1, i)$, and the second line represents the characters in the second row similarly.

Output

An integer representing the length of the longest palindrome path.

Examples

Input 1

5
pkusc
pkukp

Output 1

6

Subtasks

Subtask 1 ($30\%$): $n \le 1000$.

Subtask 2 ($20\%$): It is guaranteed that the longest palindrome path can be formed by only moving right.

Subtask 3 ($50\%$): No special restrictions.

For all test cases, $1 \le n \le 10^5$, and the strings contain only lowercase English letters.