У комп'ютерній мережі вашої фірми \(n\) комп'ютерів. Останнім часом світч, до якого вони підключені, сильно барахлить, і тому не будь-які два комп'ютери можуть зв'язатися один з одним. Крім того, якщо комп'ютер \(a\) обмінюється інформацією з комп'ютером \(b\), то ніякі інші комп'ютери не можуть в цей час обмінюватися інформацією ні з \(a\), ні з \(b\).

Вам необхідно обчислити максимальну кількість комп'ютерів, які можуть одночасно брати участь у процесі обміну інформацією.

Формат вхідних даних

У першому рядку файлу міститься число \(n\) (\(1\leqslant n\leqslant 18\)).

Далі йдуть \(n\) рядків по \(n\) символів, причому \(j\)-ий символ \(i\)-ого рядка дорівнює \(Y\), якщо \(i\)-ий і \(j\)-ий комп'ютери можуть обмінюватися інформацією, інакше він дорівнює \(N\). Правильно, що \(i\)-ий символ \(i\)-го рядка завжди дорівнює \(N\), крім того, матриця символів симетрична.

Формат вихідних даних

Виведіть максимальну кількість комп'ютерів, які можуть одночасно брати участь у процесі обміну інформацією.

Приклад вхідних даних

5
NYYYY
YNNNN
YNNNY
YNNNY
YNYYN

Приклад вихідних даних

4