코코네 초콜릿 가게에서는 밸런타인 특별 상품으로 정육각형 $3$개를 삼각형 모양으로 붙인 초콜릿을 판매하려고 한다. 코코는 같은 크기의 정육각형 $\frac{N(N+1)}{2}$개를 삼각형 모양으로 붙인 형태의 틀에 이 초콜릿들을 빈틈없이 넣어 포장하려고 한다. 그리고 이를 조금 더 예뻐 보이게 하기 위해, 위로 뾰족한 방향으로 배치된 초콜릿은 빨간색, 반대 방향의 초콜릿은 파란색으로 개별 포장을 하기로 했다. 포장이 완료된 상품은 겉에서 볼 때 각각의 육각형이 빨간색인지 파란색인지만 알 수 있고, 어느 칸들이 같은 조각인지는 알 수 없다.

코코네 가게에 놀러 온 한별이는 완성된 상품을 구경하다가, 다른 모양의 초콜릿이 들어 있는 것으로 보이는 상품을 보게 되었다. 한별이를 도와서 어느 상품이 잘못되었는지 찾아 코코에게 알려주자.

Input

첫 번째 줄에는 삼각형 틀의 한 변의 길이 $N$이 주어진다. $(1 \le N \le 5\,000)$

그다음 $N$줄에 걸쳐서 빨간색과 파란색 육각형의 배치가 공백 없이 주어진다. 빨간색은 R, 파란색은 B로 주어지며, $i$번째 줄에는 그 줄에 속하는 $i$개의 육각형에 해당하는 글자가 왼쪽부터 순서대로 주어진다. $(1 \le i \le N)$

Output

주어진 배치를 위로 뾰족한 빨간색 삼각형과 아래로 뾰족한 파란색 삼각형으로 빈틈없이 겹치지 않고 나눌 수 있으면 1, 아니면 0을 한 줄에 출력한다.

Examples

Input 1

2
R
RR

Output 1

1

Input 2

4
R
RR
RBR
RRRR

Output 2

0