Натиск!
У вас є ігрова дошка розміром n×n. Деякі клітинки містять перешкоди, за винятком крайньої лівої та крайньої правої колонок, які не містять перешкод. Крайня ліва колонка заповнена вашими n фігурами, по 1 на кожен рядок. Ваша мета — перемістити всі ваші фігури до крайньої правої колонки якомога швидше. За один хід ви можете перемістити кожну фігуру на N, S, E або W на одну клітинку, або залишити цю фігуру на місці. Фігура не може переміщатися на клітинку, що містить перешкоду, і дві фігури не можуть переміститися на одну і ту ж клітинку за один хід. Усі фігури рухаються одночасно, тому одна може переміститися на місце, яке зараз зайняте іншою фігурою, якщо ця фігура сама переміститься в інше місце одночасно.
Знаючи n та перешкоди, визначте найменшу кількість ходів, необхідних для переміщення всіх ваших фігур на праву сторону дошки.
Вхідні дані
Кожен тестовий випадок починається з додатного цілого числа n, що вказує на розмір ігрової дошки, при цьому n ≤ 25. Далі йде n рядків, що містять по n символів кожен. Якщо j-й символ у i-му рядку є 'X', то на позиції i, j дошки є перешкода; в іншому випадку цей символ буде '.', що означає відсутність перешкоди.
Ніколи не буде перешкоди в 0^ій або (n–1)^ій колонці, і завжди буде принаймні один шлях без перешкод між цими двома колонками. Рядок, що містить лише 0, завершить введення.
Вихідні дані
Для кожного тестового випадку виведіть мінімальну кількість ходів, необхідних для переміщення всіх фігур з лівої сторони дошки на праву сторону.