Mağara Tədqiqatı#3347
Uzun zaman əvvəl bir adam mağaranın dəhlizlərini araşdırdığını iddia etdi. Bu, onun mağaranın bütün dəhlizlərində olduğunu deməkdir. Dəhlizlər yalnız üfüqi və ya şaquli seqmentlərdən ibarətdir. Bir dəhliz, əgər adam onun hər hansı bir nöqtəsində olubsa, ziyarət edilmiş sayılır.
İndi siz bu iddianın doğru olub-olmadığını öyrənmək istəyirsiniz. Sizdə mağaranın xəritəsi var və bilirsiniz ki, tədqiqatçı aşağıdakı alqoritmdən istifadə edib: əgər sola dönə bilirsə, dönür; əgər dönə bilmirsə, düz gedir; əgər gedə bilmirsə, sağa dönür; əgər dönə bilmirsə, geri dönür. Tədqiqat, adam giriş nöqtəsinə ikinci dəfə çatanda sona çatır. Sizin vəzifəniz, tədqiqatçının ziyarət etmədiyi dəhlizlərin sayını hesablamaqdır.
Birinci sətirdə tam ədəd T (T ≤ 20) - müxtəlif xəritələrin sayı verilir. Hər xəritə üçün birinci sətirdə tam ədəd N (N ≤ 1000) - dəhlizlərin sayı verilir. Məlumdur ki, heç bir iki şaquli dəhliz ümumi nöqtəyə malik deyil və heç bir iki üfüqi dəhliz ümumi nöqtəyə malik deyil. Beləliklə, növbəti N sətir belə məlumatları ehtiva edir: sətir V və ya H simvollarından biri ilə başlayır - şaquli və ya üfüqi dəhliz. Sonra üfüqi dəhliz üçün bir Y-koordinatı və iki X-koordinatı və ya şaquli dəhliz üçün bir X-koordinatı və iki Y-koordinatı verilir. Hər xəritə üçün son sətir giriş nöqtəsinin X və Y koordinatlarını və istiqaməti (W - sol, E - sağ, N - yuxarı və S - aşağı) ehtiva edir. Sizə zəmanət verilir ki: giriş nöqtəsi iki dəhlizin kəsişmə nöqtəsində yerləşmir və tədqiqatçı həmişə verilən istiqamət üzrə irəliləyə bilər. Bütün koordinatlar tam ədədlərdir və mütləq dəyəri ilə 32767-dən çox deyil və ən çox 500 şaquli dəhliz və ən çox 500 üfüqi dəhliz var.
Hər xəritə üçün proqram ziyarət edilməmiş dəhlizlərin sayını ayrı sətirdə çap etməlidir.
Nümunə 1