Coco's chocolate shop is planning to sell a special Valentine's Day product consisting of chocolates shaped like three regular hexagons joined together in a triangle. Coco wants to pack these chocolates into a triangular mold made of $\frac{N(N+1)}{2}$ regular hexagons of the same size, filling it completely. To make it look more attractive, she decided to wrap the chocolates pointing upward in red and the chocolates pointing downward in blue. Once the product is packaged, one can only see whether each individual hexagon is red or blue from the outside, but it is impossible to tell which cells belong to the same chocolate piece.

Hanbyeol, who visited Coco's shop, was looking at the finished products and noticed one that appeared to contain chocolates of a different shape. Let's help Hanbyeol find out which product is incorrect and inform Coco.

Input

The first line contains the side length $N$ of the triangular mold. $(1 \le N \le 5\,000)$

The next $N$ lines contain the arrangement of red and blue hexagons without spaces. Red is represented by R and blue by B. The $i$-th line contains the characters corresponding to the $i$ hexagons in that row, given in order from left to right. $(1 \le i \le N)$

Output

If the given arrangement can be divided into upward-pointing red triangles and downward-pointing blue triangles without any gaps or overlaps, output 1; otherwise, output 0 on a single line.

Examples

Input 1

2
R
RR

Output 1

1

Input 2

4
R
RR
RBR
RRRR

Output 2

0