Stampede!
Sizin n×n ölçüsündə bir oyun taxtanız var. Bəzi kvadratlarda maneələr mövcuddur, lakin sol və sağ sütunlar maneəsizdir. Sol sütun sizin n fiqurunuzla doludur, hər biri 1 sırada yerləşir. Məqsədiniz bütün fiqurlarınızı mümkün qədər tez sağ sütuna keçirməkdir. Hər bir növbədə, hər bir fiquru N, S, E və ya W istiqamətində bir kvadrat hərəkət etdirə bilərsiniz və ya həmin fiquru yerində saxlaya bilərsiniz. Fiqur maneə olan kvadrata keçə bilməz, həmçinin eyni növbədə iki fiqur eyni kvadrata keçə bilməz. Bütün fiqurlar eyni anda hərəkət edir, belə ki, bir fiqur başqa bir fiqurun hazırda yerləşdiyi yerə keçə bilər, əgər həmin fiqur da eyni zamanda başqa yerə keçirsə.
Verilən n və maneələrə əsasən, bütün fiqurlarınızı taxtanın sağ tərəfinə keçirmək üçün lazım olan ən az növbə sayını müəyyən edin.
Giriş verilənləri
Hər test halı oyun taxtasının ölçüsünü göstərən müsbət tam ədəd n ilə başlayır, burada n ≤ 25. Bundan sonra n sətir olacaq, hər biri n simvolu ehtiva edir. Əgər i-ci sətirdəki j-ci simvol 'X'dirsə, onda taxtanın i, j yerində maneə var; əks halda bu simvol maneənin olmadığını göstərən '.' olacaq.
Heç vaxt 0-cı və ya (n–1)-ci sütunda maneə olmayacaq və bu iki sütun arasında həmişə maneəsiz bir yol olacaq. Tək 0 olan bir sətir girişi bitirəcək.
Çıxış verilənləri
Hər test halı üçün fiqurların taxtanın sol tərəfindən sağ tərəfinə keçməsi üçün lazım olan minimum növbə sayını çıxarın.