В компьютерной сети вашей фирмы \textbf{n} компьютеров. В последнее время свитч, к которому они подключены, сильно барахлит, и потому не любые два компьютера могут связаться друг с другом. Кроме того, если компьютер \textbf{a} обменивается информацией с компьютером \textbf{b}, то никакие другие компьютеры не могут в это время обмениваться информацией ни с \textbf{a}, ни c \textbf{b}. Вам необходимо вычислить максимальное количество компьютеров, которые могут одновременно участвовать в процессе обмена информацией. \InputFile В первой строке файла задано число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{18}). Далее идут \textbf{n} строк по \textbf{n} символов, причем \textbf{j} символ \textbf{i}-й строки равен "\textbf{Y}", если \textbf{i}-й и \textbf{j}-й компьютеры могут обмениваться информацией, иначе он равен "\textbf{N}". \textbf{i}-й символ \textbf{i}-й строки всегда равен "\textbf{N}", кроме того, матрица символов симметрична. \OutputFile Выведите максимальное количество компьютеров, которые могут одновременно участвовать в процессе обмена информацией.