给定一个 2×n 的网格,左上角的格子编号为 (1,1),右下角为 (2,n)。每个格子有一个字符(只包含小写字母),你可以从任意格子开始,每一步向右或向下移动,然后在任意格子停止。容易发现这样走出来的一定是一条简单路径(即经过每个格子一次)。
若将一条路径的字符按走的顺序取出组成的字符串是回文串,则称这条路径是回文路径。定义路径的长度为经过格子的个数,你需要求出最长的回文路径的长度是多少。
Input
第一行一个正整数 n。
接下来两行,每行为一个长为 n 的字符串,第一行的第 i 个字符表示格子 (1,i) 里的字符,第二行同理。
Output
一个整数表示最长的回文路径的长度。
Example
Input
5 pkusc pkukp
Output
6
Scoring
Subtask1 (30%): n≤1000。
Subtask2 (20%): 保证只往右走就能走出最长的回文路径。
Subtask3 (50%): 无特殊限制。
对于所有数据,1≤n≤105,字符串只包含小写字母。