Placid subsets P68087

You are planning a trip for the $n$ members of a club. However, some of the members dislike other members. Therefore, you decide to choose a subset $S$ of members such that:

• Inside $S$, noone dislikes anyone.

• There is no $S'$ such that $S \subset S'$ and such that $S'$ fulfils the first property. In other words, $S$ must be maximal.

Given the information about who dislikes who, can you count the number of such subsets?

Input

Input consists of several cases, each one with $n$ followed by $n$ lines with $n$ characters each. For $i \ne j$, the $j$-th character of the $i$-th line is ‘L’ or ‘D’ depending on whether $i$ likes or dislikes $j$. The diagonal has only dots. Assume $1 \le n \le 20$.

Output

For every case, print the number of maximal placid subsets.