Непередбачувані мурахи
Мурахи з певної колонії шукають їжу. На жаль, навколо колонії повно прихованих небезпек, що ускладнює пошуки. Є пастки, перешкоди та хижаки, які чатують навколо. На щастя, у колонії є ідеальна мураха для цієї роботи. Макс не є ані розумною, ані ефективною мурахою, але йому завжди щастить. У всіх своїх мандрах він завжди вдається залишатися на безпечній території, і він (зрештою) завжди знаходить джерело їжі, щоб повідомити про це колонії.
Проблема полягає в тому, що Макс рідко обирає щось схоже на оптимальний (найкоротший) шлях до джерела їжі. Однак, Макс може надійно повернутися з точними деталями (часто звивистого і заплутаного) шляху, яким він пройшов до джерела їжі. Ваше завдання - допомогти колонії, знайшовши оптимальний шлях у заплутаних вказівках Макса, щоб колонія могла ефективніше шукати їжу.
Вхідні дані
Перше ціле число у вхідних даних, 1 ≤ n ≤ 100, позначає кількість шляхів до їжі, про які повідомив Макс. За цим слідує порожній рядок, а потім описи кожного з n шляхів. Кожен опис шляху починається з цілого числа, s (0≤ s ≤ 60), яке позначає кількість кроків, зроблених на шляху. Наступні s рядків містять кроки напрямку, виражені великими літерами N, E, S та W, що відповідають крокам у напрямках північ, схід, південь та захід відповідно. Кожен крок переміщує Макса на одну одиницю відстані. Шляхи Макса завжди починаються в колонії і закінчуються біля джерела їжі. Між кожною парою описів шляхів є порожній рядок.
При пошуку оптимального шляху єдині кроки напрямку, які можуть бути зроблені, це ті, які раніше були зроблені Максом, або ті ж самі кроки у зворотному напрямку.
Вихідні дані
Для кожного заданого шляху вкажіть кількість кроків, які виявилися в оптимальному (найкоротшому) шляху.