환영 추격

로봇 고양이 톰이 로보틱스 전시회에서 어린 관객들 앞에 놓인 $m \times n$ 크기의 필드 위에 세워집니다. 처음에는 꺼져 있는 톰을, 관객 중 한 명이 필드 위 임의의 칸에 올려놓습니다. 쇼가 시작되는 시각 0에 톰은 리모컨으로 켜집니다.

톰의 눈앞 조금 떨어진 곳에 제리의 홀로그램 환영이 나타납니다. 톰과 환영 사이의 직선 경로는 항상 수평 또는 수직이며, 그 경로 위에는 장애물이 하나도 없습니다. 톰은 제리에게 다가가지만, 도착하는 순간 환영은 다른 자리로 옮겨 가고 추격이 계속됩니다. 한 방향(위, 아래, 왼쪽, 오른쪽)으로 이어지는 각 추격을 추격 이동이라고 부릅시다. 각 이동은 직전 환영이 있던 칸에서 시작해 다음 환영이 나타나는 칸에서 끝납니다. 여러 번의 추격 이동 뒤에 환영은 더 이상 나타나지 않고, 톰은 다음에 무엇을 해야 할지 고민합니다. 이때 톰은, 추격을 시작한 처음 그 자리로 돌아가면 진짜 제리가 잠들어 있어 잡을 수 있다는 신호를 받습니다.

문제를 단순화하기 위해 필드를 정사각형 칸들의 격자로 봅시다. 일부 칸은 장애물로 막혀 있습니다. 어느 순간에도 톰은 비어 있는 칸에 있고, 제리(환영) 역시 비어 있는 칸에 있으며, 둘 사이의 직선 경로는 수평 또는 수직입니다. 톰은 환영을 볼 때마다, 장애물에 부딪히지 않고 네 방향 중 한 방향으로만 움직여 도달할 수 있습니다. 톰은 한 번에 정확히 한 칸씩 인접한 칸으로 이동합니다.

문제는 톰의 기록 장치가 다소 부정확하다는 점입니다. 그래서 각 추격 이동에서 톰이 이동한 걸음 수는 정수 구간으로 기록됩니다(예: 왼쪽으로 2걸음에서 5걸음). 이제 톰이 돌아갈 수 있도록 프로그램을 작성할 차례입니다. 다만 이 대회에서는 과제를 쉽게 하기 위해, 톰이 추격을 시작했을 수 있는 모든 칸의 개수만 세면 됩니다.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 10$)가 주어지고, 이어서 각 테스트 케이스의 입력이 주어집니다. 각 테스트 케이스의 첫 줄에는 격자의 행 수와 열 수를 나타내는 두 정수 $m$과 $n$이 주어집니다 ($1 \le m, n \le 100$). 그다음 $m$개의 줄에 각각 $n$개의 정수가 주어지며, 각 값은 0 또는 1로, 해당 칸이 비어 있으면(0), 장애물이 있으면(1)임을 나타냅니다.

필드 설명 다음에는 톰의 추격 이동을 순서대로 나타내는 줄들이 이어집니다. 각 줄에는 톰이 이동한 걸음 수의 범위(양 끝 포함)를 나타내는 두 양의 정수와, 추격 방향을 나타내는 대문자 한 글자가 주어집니다. 방향은 R(오른쪽), L(왼쪽), U(위), D(아래) 중 하나입니다. (이 방향들은 필드를 기준으로 한 것이며, 톰이 바라보는 방향과는 무관합니다.) 이 부분은 정확히 두 개의 0으로 이루어진 줄로 끝납니다.

각 테스트 케이스마다, 톰이 추격을 시작했을 수 있는 칸의 개수를 나타내는 정수 하나를 한 줄에 출력합니다.