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 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.
For each test case, write a single line which gives the maximum number of nodes that can communicate simultaneously.
5 NYYYY YNNNN YNNNY YNNNY YNYYN