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.

Public test cases

**Input**

2 .D L. 5 .LDDL D.LDL DL.LL LDD.D LLLL. 6 .LLLLL L.LLLL LL.LLL DLL.LL LLDL.L LLLDD.

**Output**

2 3 4

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++