描述

有一列长度为$N+2$的格子，前$N$个格子分别预先摆好了一颗宝石，分别是"A"宝石或"B"宝石，最后两个格子是空的。

每次可以将任意两个相邻的格子的宝石顺序不变的放到空的格子里，称为一次操作。

问，能否经过有限次的操作，把宝石变成目标的样子，如果能，输出最少的操作次数，否则，输出-1。

输入输出格式

输入

第一行为一个正整数 $N$，表示原来有多少个宝石。 ($1 ≤ N ≤ 20$)

第二行为一个长度为$N$，仅包含"A"或"B"的字符串，表示一开始的宝石排列。

第三行为一个长度为$N$，仅包含"A"或"B"的字符串，表示目标的宝石排列。

输出

一个整数，如果能变成目标排列，输出最少的操作次数，否则输出-1。

样例

6
ABABAB
AAABBB

4

样例1说明

注： 以下用"."表示空位

• ABABAB..
• ABA..BBA
• ABABB..A
• A..BBBAA
• AAABBB..

通过四次操作可以完成变换。