题目描述

设 $X=x_1x_2\cdots X_n$ 是一个给定的基因序列。其中 $x_i \in \{A, C, G, T\}, \forall 1 \leq i \leq n$。

对于一个基因序列 $X$，我们称它的 $i$ 位移（$1 \leq i \leq n$）为 $X$ 的后 $i$ 位与 $X$ 的前 $n-i$ 位拼接而成的字符串。一个基因序列的特征定义为它的字典序最小的位移。

对于两个基因序列，我们称它们相似当且仅当它们的特征相等。

最长公共相似子序列问题是要求对于给定的两个长度相同的基因序列 $X=x_1x_2\cdots x_n$ 和 $Y=y_1y_2\cdots y_n$，计算其最长公共相似子序列的长度。

编程任务

对于给定的两个长度相同的基因序列 $X=x_1 x_2 \cdots x_n$ 和 $Y= y_1y_2\cdots y_n$，计算其最长公共相似子序列的长度。

输入格式

输入的第一行包含一个正整数 $n$。

接下来两行分别给出输入序列 $X=x_1x_2\cdots x_n$ 和 $Y=y_1y_2\cdots y_n$。其中序列中每个元素均为 $\{A,C,G,T\}$ 中的字母。

输出格式

输出一行一个整数表示答案。当不存在公共相似子序列时，输出 $0$。

样例数据

样例输入

6
CCAGTA
ATAGTC

样例输出

4

子任务

对于 $10\%$ 的数据，$n \leq 10$。

对于 $40\%$ 的数据，$n \leq 300$。

对于 $70\%$ 的数据，$n \leq 1000$，保证数据随机生成。

对于 $100\%$ 的数据，$n \leq 2000$。