Муравьи некоторой колонии находятся в поисках пищи. К сожалению, скрытые опасности находятся везде вокруг колонии, что затрудняет кормление. Там скрываются ловушки, препятствия и хищники. К счастью, колония имеет идеального муравья для работы во вне. Макс не является ни умным, ни мужественным муравьем, зато слепая удача всегда на его стороне. Во всех своих скитаниях ему всегда удавалось твердо стоять на ногах, и он (в конце концов) всегда находил источник пищи, чтобы отчитаться перед колонией.
Проблема в том, что Макс редко выбирает оптимальный (самый короткий) маршрут, чтобы найти источник пищи. Однако Макс может достоверно сообщить точные детали пути (часто извилистого и запутанного), по которому он шел, чтобы добраться до источника пищи. Ваша задача - помочь колонии, найдя оптимальный маршрут среди извилистых направлений Макса, чтобы позволить колонии более эффективно прокормиться.
Ввод состоит из нескольких тестов. Первая строка содержит количество тестов n, 1≤n≤100. Каждый тест начинается с пустой строки. Следующая строка содержит число s, 1≤s≤60 - количество шагов в пути Макса. Слудующие s строк содержат по одному символу из набора N, E, S, W, соответствующие направлению одного шага Макса соответственно на север, запад, юг и восток. Путь Макса всегда начинается в колонии и заканчивается в источнике пищи.
При поиске оптимального пути можно использовать только те же шаги, которые делал Макс.
Для каждого теста выведите количество шагов в оптимальном пути.
| Sample input | Sample Output |
|---|---|
3 8 S E E E N W S S 4 S E N W 3 S E N |
4 0 3 |