EOJ Test Round #2 (Warm-up Contest for Lanqiao)

F. God and Gods

单点时限: 2.0 sec

内存限制: 256 MB

起初,世界上没有题,没有做题的人。

第一天,上帝说,要有 AGCT,于是就有了 AGCT。

第二天,上帝说,要有题,然后就有了一道有关 AGCT 的题。

第三天,上帝喊来了众神,让他们创造两个只含有 AGCT 的字符串,于是众神们就创造了两个字符串。

第四天,上帝说,这两个字符串既要相等,又要是正回文串(字符串倒置后与本身相等,且长度为奇数),要让众神重新造。众神有点不悦,他们决定从原先的两个字符串中分别找出一个连续子串。

第五天,上帝说,这个子串要尽量长。众神皆勃然大怒,拂袖而去,留下你在这做题。

输入格式

两行。

每一行分别由一个数 (n) ((1 \leq n \leq 10^5)) 开头,然后是一个长度为 (n) 的字符串,仅有大写英文字母 A, G, C, T 组成。

对于约 40% 的数据,有 (n \leq 10^3)。

输出格式

输出一个整数:最长的公共正回文子串的长度。

样例

Input
12 AGCGCGATTTTT
14 ATTTTTTACGCGCA
Output
5
Input
10 AGCGATTTTT
11 ATTTTTTACGCA
Output
5
Input
10 ACGATCGGAT
13 AGCGATGCGTACG
Output
1