Risk
Risk, dünya xəritəsində oynanan bir stolüstü oyundur. Bu dünya, sərhədlərlə ayrılmış bölgələrə bölünür. Hər bir bölgə ya sizin, ya da rəqiblərinizdən birinin nəzarətindədir. Nəzarət etdiyiniz hər bölgədə müsbət sayda ordunuz var.
Hər turda ordularınızı hərəkət etdirmək hüququnuz var. Hər bir ordu ya olduğu yerdə qala bilər, ya da nəzarətinizdə olan sərhəd bölgəsindən başqa bir bölgəyə keçə bilər. Hərəkətlər sizin seçdiyiniz sıraya uyğun olaraq tək-tək həyata keçirilir. Hər zaman hər bir bölgədə ən az bir ordu olmalıdır.
Strateji məqsədlər üçün, ordularınızı rəqiblərinizin bölgələri ilə sərhəd olan bölgələrə köçürmək və tamamilə nəzarətinizdə olan digər bölgələrlə əhatə olunmuş bölgələrdəki orduların sayını minimuma endirmək vacibdir. Ən zəif həlqənizin, yəni ən az sayda ordu olan sərhəd bölgənizin mümkün qədər güclü olmasını istəyirsiniz. Bir turdan sonra ora yerləşdirilə biləcək maksimum ordu sayını nə qədərdir?
Giriş verilənləri
Birinci sətirdə müsbət tam ədəd: test hallarının sayı, ən çox 100. Bundan sonra hər test halı üçün:
Bir sətirdə tam ədəd n (1 ≤ n ≤ 100): bölgələrin sayı.
Bir sətirdə n tam ədəd a_i (0 ≤ a_i ≤ 100): hər bölgədəki ordularınızın sayı. 0 rəqəmi bir bölgənin rəqibləriniz tərəfindən idarə olunduğunu, müsbət rəqəm isə sizin idarənizdə olduğunu göstərir.
n sətirdə n simvol, hər simvol ya 'Y', ya da 'N'. i-ci sətirin j-ci simvolu, bölgələr i və j sərhəddədirsə 'Y', əks halda 'N' olacaq. Bu əlaqə simmetrikdir və i-ci sətirin i-ci simvolu həmişə 'N' olacaq.
Hər test halında, ən az bir bölgəni idarə edirsiniz və rəqibləriniz ən az bir bölgəni idarə edir. Üstəlik, bölgələrinizdən ən az biri rəqiblərinizin bölgələrindən ən az biri ilə sərhəddədir.
Çıxış verilənləri
Hər test halı üçün:
Bir sətirdə tam ədəd: bir tur hərəkətdən sonra ən zəif sərhəd bölgənizdəki maksimum ordu sayı.