Првата функционалност која ја понудил Фејзбук на корисниците (студентите на Харвард) е да имаат можност за пар од два студента да може да кажат дали првиот од нив е поатрактивен од вториот. Се разбира, правејќи ја оваа прва верзија на апликацијата, авторите покрај тоа што прекршиле права за користење на фотографиите на студентите, вклучиле функција за која може да се дискутира дали е пристојна или се граничи со невкус.

Да речеме дека во даден момент тие имале М корисници и за секој пар (А, В) од нив имале добиено одговор (од некој од корисниците) дали првиот корисник е поатрактивен од вториот. Одговорот можел да биде ДА или НЕЗНАМ. Внимавајте, за истиот пар корисници тие имаат и оценка и за случај (В, А) која е дадена од некој друг корисник и таа може да е и контрадикторна на оценката од претходно.

Нека овие податоци се дадени во една М x М шема, каде во секое поле е запишана буквата ‘D’ (ако А е поатрактивен од В, т.е. даден е одговор ДА) или буквата ‘N’ (ако е даден одговор НЕЗНАМ).

Се разбира, одговорите за атрактивност се субјективни, и гледајќи ги сите одговори можеби нема да постои начин да се подредат сите М корисници од најатрактивен до најмалку атрактивен. Ние сакаме да направиме да постои начин да ги подредиме корисниците, па ако треба и да мамиме, на тој начин што ќе направиме неколку измени во шемата. Една измена претставува одбирање на точно едно поле и промена на буквата во него - од ‘D’ во ‘N’ или од ‘N’ во ‘D’.

Пресметајте колку најмалку измени треба да се направат за да може да се направи подредување во кое ако знаеме дека за парот корисници (А, В) е даден одговор ДА, тогаш А ќе се појави пред В во подредувањето.

Влез

Во првиот ред е даден бројот на корисници M (1 ≤ M ≤ 20).
Во следните M редови се дадени по M знаци кои ја опишуваат шемата, според објаснувањето дадено во текстот. Секој од овие знаци е или ‘D’ или ‘N’.
Загарантирано е дека за секоја редица r, r-тиот знак во истата е ‘N’.

За 5% од поените ќе важи: M = 2
За дополнителни 25% од поените ќе важи: 1 ≤ M ≤ 9
За дополнителни 30% од поените ќе важи: 1 ≤ M ≤ 15

Излез

Во еден ред отпечатете го бараниот минимален број на измени.

Ограничувања

Временско ограничување: 200 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
2
ND
DN

излез
1

Објаснување за првиот пример: Од примерот се гледа дека корисникот 1 мора да e подреден пред корисникот 2. Но, исто така, корисникот 2 мора да е подреден пред корисникот 1. Па затоа доволна е една измена: или во полето (1, 2) или во полето (2, 1).