Накрыв стол и ведя приятную беседу, наши герои рассказали мистеру Нетворку о своём путешествии по миру. "Я вижу ви любите решать интересные задачи?" – сказал мистер Нетворк – "Тогда получайте ещё одну из моей производственной практики".
"Однажды я занимался настройкой компьютерной сети на фирме, где тогда работал. Фирма имела N компьютеров. Свич, к которому были подсоединены все компьютеры, начал сильно сбоить, и поэтому не любые два компьютера могли связаться друг с другом. Кроме того, если компьютер A обменивался информацией с компьютером B, то никакие другие компьютеры не могли в это время обмениваться информацией ни с A, ни с B. Вам необходимо вычислить максимальное количество компьютеров, которые могли одновременно принимать участие в процессе обмена информацией" – завершил свой рассказ мистер Нетворк.
В первой строке файла задано целое число N (1 ≤ N ≤ 18). Далее идут N строк по N символов, причём j-ый символ i-ой строки равен 'Y', если i-ый и j-ый компьютеры могут обмениваться информацией, иначе он равен 'N'. i-ый символ i-ой строки всегда равен 'N', кроме того, матрица символов симметрична.
Выведите максимальное количество компьютеров, которые могут одновременно принимать участие в процессе обмена информацией.