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 ⊂ 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 ≠ 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 ≤ n ≤ 20.

Output

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