#1572 Separate Connections

34  5 s   128 MB  

Description

You are analyzing a communications network with at most 18 nodes. Assuming a node cannot communicate with two nodes at once, compute the maximum number of nodes that can communicate simultaneously.

Input

Input consists of several test cases.

The first line of each test cases contains a positive integer N, the number of nodes in the communication network. The following N lines contain exactly N character per line and describe a matrix mat. j-th Character in i-th row of mat denotes whether nodes i and j can communicate ('Y' for yes, 'N' for no). You may assume that if node s is communicating with node t then node t is communicating with node s. i-th character of i-th row will be always 'N'.

Note that 1 ≤ N ≤ 18 for all test cases. Input is terminated by EOF.

Output

For each test case, write a single line which gives the maximum number of nodes that can communicate simultaneously.

Sample Input

Sample Output

5
NYYYY
YNNNN
YNNNY
YNNNY
YNYYN
4