SingleDog们设法进入了核心，他们发现，三台TPU主机的程序混在了一起，每个主机对应一种颜色，屏幕上出现了斑斓的色条！

具体来说，他们发现了一个长度为$n$的颜色串，每个位置是红/蓝/绿（记为 R/G/B ）三个颜色中的一种。为了彻底杜绝AlphaGo的朋友圈狗粮，他们需要把这部分代码完全改写。

根据跳蚤国王发来的消息，每次你可以选择相邻的两个色块，进行一次操作，为了方便理解，记操作前的两个位置的颜色为 $c_a,c_b$ ，操作后的为 $c_a^{{}^{\prime }},c_b^{{}^{\prime }}$ 。

1. 如果你选择的两个色块是同色（ $c_a=c_b$ ），你可以把它们变成两种不同的新颜色（即 $c_a^{{}^{\prime }}\ne c_b^{{}^{\prime }},c_a\ne c_a^{{}^{\prime }},c_b\ne c_b^{{}^{\prime }}$ ），例如，当你选择了 GG 后，你可以将它们变为 RB 或 BR。
2. 如果你选择的两个色块是异色（ $c_a\ne c_b$ ），你可以把它们变成两种相同的新颜色（即 $c_a^{{}^{\prime }}=c_b^{{}^{\prime }},c_a\ne c_a^{{}^{\prime }},c_b\ne c_b^{{}^{\prime }}$ ），例如，当你选择了 RB 后，你可以将它们变为 GG 。

你的目标是把这串代码从状态 $S$ 变为状态 $T$ ，求最小步数。

输入格式

第一行一个正整数 $n$ ，表示这串代码的长度。

第二行一个长度为 $n$ 的字符串 $S$ ，表示这串代码的起始状态。

第三行一个长度为 $n$ 的字符串 $T$ ，表示这串代码的终止状态。

输出格式

输出一行一个整数，表示把这串代码从状态 $S$ 变为状态 $T$ 的最小步数。

样例一

input

3
GBR
BBB

output

3

explanation

第一次操作将 GB 改为 RR ，操作后的代码为 RRR 。

第二次操作将 RR 改为 BG ，操作后的代码为 BGR 。

第三次操作将 GR 改为 BB ，操作后的代码为 BBB 。

可以证明没有次数更少的操作序列。

样例二

input

4
GBRB
GRRG

output

2

explanation

第一次操作将 RB 改为 GG ，操作后的代码为 GBGG 。

第二次操作将 BG 改为 RR ，操作后的代码为 GRRG 。

可以证明没有次数更少的操作序列。

样例三

input

20
RBBGRBBGRBBBBGRBRGGB
RBGRRBRBGBRRGBBBGBGG

output

14

限制与约定

保证 $S$ 和 $T$ 只由大写字母 'R','G','B' 组成，保证存在一组操作方案将代码的状态从 $S$ 变为 $T$ 。

时间限制：$2\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

友情提示：题目难度和题目顺序没有关系

下载

样例数据下载