AlgoLiga 2018

Zorganizowanie regat żaglowców na otwartym morzu to doprawdy niemałe wyzwanie. Nigdy nie wiadomo czy zawodnikom w ogóle uda się dotrzeć do celu (w końcu cały czas mogą wiać niepomyślne wiatry) i kiedy ewentualnie może dopłynąć pierwszy z nich (na tę okoliczność trzeba zaprosić w odpowiednim czasie rzeszę paparazzi i całą dyrekcję).

Organizatorzy postanowili przygotować się do tegorocznej edycji imprezy wyjątkowo dokładnie i zamówili w tym celu bardzo szczegółowe mapy pogodowe. Jak wynika z map codziennie od rozpoczęcia do zakończenia regat przez cały dzień wiatr będzie wiał tylko w jednym z czterech kierunków (północnym, wschodnim, południowym albo zachodnim). Fakt ten powinien zdecydowanie uprościć wszelkie obliczenia ponieważ regulamin zakłada, iż zawodnik wraz ze wschodem słońca musi ustalić czy na dzisiejszy dzień rozłoży żagle i przepłynie jedną jednostkę odległości zgodnie z kierunkiem wiatru czy też żagle pozostaną złożone a zawodnik nie zmieni swego położenia przez najbliższe 24 godziny. Oczywiście wszyscy organizatorzy z zawodu są dyrektorami tak więc nie mają pojęcia jak obliczyć interesujące ich dane w związku z czym za promil swojej pensji postanowili zatrudnić do tego zadania właśnie Ciebie.

Wejście

W pierwszej linii wejścia znajduje się liczba n (1 ≤ n ≤ 100) określająca liczbę zestawów danych. Każdy zestaw w pierwszym wierszu zawiera współrzędne s_x, s_y, m_x, m_y (z zakresu od -10⁹ do 10⁹) określające współrzędne punktów startu oraz mety, a także liczbę d (1 ≤ d ≤ 10⁵) opisującą na ile dni organizatorzy posiadają mapy pogodowe. Drugi wiersz każdego zestawu składa się z ciągu liter N, E, S, W określających w jakim kierunku będzie wiał wiatr danego dnia (pierwsza litera określa sytuację pierwszego dnia, druga drugiego itd.)

Wyjście

Na wyjściu, w oddzielnej linii dla każdego zestawu danych, należy wypisać liczbę dni po jakich do mety dopłynąć może najszybszy zawodnik lub słowo NIE jeżeli warunki pogodowe uniemożliwiają ukończenie wyścigu na przestrzeni d dni.

Przykład

Wejście:

2
4 -4 2 1 11
NNWWEEESNNN
3 2 7 6 12
NNNEEENNWWSS

Wyjście:

11
NIE