Coco 的巧克力店计划推出一款情人节特别商品，这是一种由 $3$ 个正六边形拼接成三角形形状的巧克力。Coco 计划将这些巧克力无缝地装入一个由 $\frac{N(N+1)}{2}$ 个相同大小的正六边形拼接成三角形形状的模具中。为了让商品看起来更美观，朝上尖方向放置的巧克力采用红色包装，相反方向（朝下尖）放置的巧克力采用蓝色包装。包装完成后，从外面只能看到每个六边形是红色还是蓝色，而无法得知哪些格子属于同一块巧克力。

来到 Coco 店里玩耍的 Hanbyul 在欣赏完工的商品时，发现有些商品似乎装有其他形状的巧克力。让我们帮助 Hanbyul 找出哪些商品是错误的，并告诉 Coco 吧。

输入格式

第一行包含三角形模具的边长 $N$。$(1 \le N \le 5\,000)$

接下来的 $N$ 行，每行无空格地给出红色和蓝色六边形的排列。红色用 R 表示，蓝色用 B 表示。第 $i$ 行从左到右依次给出属于该行的 $i$ 个六边形对应的字母。$(1 \le i \le N)$

输出格式

如果给定的排列可以无缝且不重叠地划分为朝上尖的红色三角形和朝下尖的蓝色三角形，则输出 1，否则输出 0。

样例

输入样例 1

2
R
RR

输出样例 1

1

输入样例 2

4
R
RR
RBR
RRRR

输出样例 2

0