QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[-19]

# 8668. 回文路径

Statistics

给定一个 2×n 的网格,左上角的格子编号为 (1,1),右下角为 (2,n)。每个格子有一个字符(只包含小写字母),你可以从任意格子开始,每一步向右或向下移动,然后在任意格子停止。容易发现这样走出来的一定是一条简单路径(即经过每个格子一次)。

若将一条路径的字符按走的顺序取出组成的字符串是回文串,则称这条路径是回文路径。定义路径的长度为经过格子的个数,你需要求出最长的回文路径的长度是多少。

Input

第一行一个正整数 n

接下来两行,每行为一个长为 n 的字符串,第一行的第 i 个字符表示格子 (1,i) 里的字符,第二行同理。

Output

一个整数表示最长的回文路径的长度。

Example

Input

5
pkusc
pkukp

Output

6

Scoring

Subtask1 (30%): n1000

Subtask2 (20%): 保证只往右走就能走出最长的回文路径。

Subtask3 (50%): 无特殊限制。

对于所有数据,1n105,字符串只包含小写字母。