You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Reimu 想要去找金发小女孩，但是意外来到一片红白格子组成的场地，Reimu想要快点离开这里，所以要你帮她解决这个问题。

Description

Reimu 来到一个 $2⋅n$ 个格子组成的的场地,有些格子是红色的，有些是白色的。

Reimu 可以一开始选择一个红色的格子，在接下来每一步中，可以选择在上面，下面，左边或右边的一个红色格子。当Reimu离开当前格子时，格子会立即变成白色

Reimu 想知道她能走的最大步数。

如果没有初始红色格子，请输出$0$。

Format

Input

第一行包含一个正整数$n(1≤n≤10^6)$. 接下来的两行包含 $2⋅n$ 字符矩阵，仅由‘R’和‘W’字符组成。“R”代表红色格子，“W”代表白色格子。

Output

一个整数，表示Reimu能走的最大步数 。

Samples

4
RWRW
RRRR

4

4
WWWW
WWWW

0

Limitation

1s, 5i2MiB for each test case.