P1053编辑字符串（edit）

【题目描述】

小 X 负责校对一圈首尾相接的电子字幕。字幕中共有 $n$ 个字符位置，依次编号为 $1,2,\ldots,n$，其中位置 $1$ 与位置 $n$ 也相邻。

编辑器中当前保存的字符串为 $s$，校对完成后的目标字符串为 $t$。编辑器只有一个光标，初始位于位置 $1$。每次操作，小 X 可以选择下列两种方式之一：

• 将光标顺时针或逆时针移动到相邻位置。
• 将光标所在位置的字符修改为任意一个小写英文字母。

每次移动或修改都算作一次操作。完成编辑字符串的工作后，光标可以停留在任意位置。

请你帮助小 X 求出，将字符串 $s$ 修改为字符串 $t$ 所需的最少操作次数。

【输入格式】

从文件 $\textbf{\textit{edit.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含一个正整数 $n$，表示字符串的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，表示编辑器中当前保存的字符串。

第三行包含一个长度为 $n$ 的字符串 $t$，表示校对完成后的目标字符串。

字符串 $s,t$ 均只包含小写英文字母。

【输出格式】

输出到文件 $\textbf{\textit{edit.out}}$ 中。

对于每组测试数据，输出一行一个非负整数，表示将字符串 $s$ 修改为字符串 $t$ 所需的最少操作次数。

【样例 1 输入】

10 1263abcdef4abxdxf

【样例 1 输出】

16

【说明/提示】

【样例 1 解释】

只有位置 $3,5$ 的字符需要修改。光标可以依次到达这两个位置并完成修改，共执行 $4$ 次移动与 $2$ 次修改，因此答案为 $6$。

【样例 2】

见选手目录下的 $\textbf{\textit{edit/edit2.in}}$ 和 $\textbf{\textit{edit/edit2.ans}}$。

该组样例符合测试点 $1\sim4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{edit/edit3.in}}$ 和 $\textbf{\textit{edit/edit3.ans}}$。

该组样例符合测试点 $5\sim8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{edit/edit4.in}}$ 和 $\textbf{\textit{edit/edit4.ans}}$。

该组样例符合测试点 $9\sim12$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{edit/edit5.in}}$ 和 $\textbf{\textit{edit/edit5.ans}}$。

该组样例符合测试点 $13\sim16$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{edit/edit6.in}}$ 和 $\textbf{\textit{edit/edit6.ans}}$。

该组样例符合测试点 $17\sim20$ 的数据范围。

\newpage

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq n\leq10^5$，单个测试点内所有测试数据满足 $\sum n\leq10^5$。

特殊性质 A：对于每组测试数据，满足 $s_i\neq t_i$ 的位置不超过两个。

特殊性质 B：对于每组测试数据，满足 $s_i\neq t_i$ 的位置在环上构成一个连续区间。

对于所有测试数据，保证：

• $0\leq c\leq20$，$1\leq T\leq10$。
• 字符串 $s,t$ 的长度均为 $n$，且只包含小写英文字母。