Дослідження печер#3347
Давно один чоловік заявив, що дослідив усі коридори печери. Це означає, що він побував у кожному коридорі печери. Коридори є горизонтальними або вертикальними відрізками. Коридор вважається відвіданим, якщо чоловік побував хоча б в одній точці цього коридору.
Тепер ви хочете перевірити правдивість його слів. У вас є карта печери, і відомо, що дослідник використовував наступний алгоритм: він повертає наліво, якщо це можливо; якщо ні, йде прямо; якщо і це неможливо, повертає направо; якщо жоден з цих варіантів недоступний, повертає назад. Дослідження завершується, коли чоловік вдруге досягає точки входу. Ваше завдання — підрахувати, скільки коридорів залишилося невідвіданими дослідником.
У першому рядку знаходиться ціле число (T \le 20) — кількість різних карт. Для кожної карти в першому рядку подано ціле число (N \le 1000) — кількість коридорів. Відомо, що жодні два вертикальні коридори не перетинаються, і жодні два горизонтальні коридори не перетинаються. Наступні рядків містять таку інформацію: рядок починається з одного з символів або — вертикальний або горизонтальний коридор. Далі вказується одна -координата і дві -координати для горизонтального коридору або одна -координата і дві -координати для вертикального коридору. Останній рядок для кожної карти містить і координати точки входу (початкова і кінцева точка подорожі) і напрямок ( — ліворуч, — праворуч, — вгору і — вниз). Ви можете припустити, що: точка входу не знаходиться в точці перетину двох коридорів, і дослідник завжди може рухатися вперед у напрямку, вказаному у вхідних даних. Усі координати є цілими числами і не перевищують за абсолютним значенням, і не більше ніж вертикальних коридорів і не більше ніж горизонтальних коридорів.
Для кожної карти програма повинна вивести кількість невідвіданих коридорів у окремому рядку.
Приклад 1