CF2034C.Trapped in the Witch's Labyrinth

在《列王纪》传奇英雄鲁斯塔姆的第四个任务中，一个老女巫创造了一个迷宫来困住他。迷宫是一个 $n\times m$ 的矩形网格，迷宫中每一个单元格都有箭头，指向上、下、左或右的一个特定方向。女巫对鲁斯塔姆施了魔法，他每进入一个单元格，都会按照箭头的方向移动到下一个单元格。

如果鲁斯塔姆可以离开迷宫，他将战胜女巫。否则他将永远被困在迷宫中。

还有一些单元格的方向没有被女巫确定，她希望你指定一些方向，使得鲁斯塔姆能够被困住的起始格最多。你的任务是找到使得鲁斯塔姆被困住的最多起始单元格数。

第一行，一个整数 $t$ ($1\le t\le 10^4$)，表示数据组数。

对于每组数据：

• 第一行，两个整数 $n,m$ ($1\le n,m\le 1000$)，表示迷宫的行数和列数。
• 接下来的 $n$ 行，每行 $m$ 个字符，表示这个迷宫。每个字符都是以下之一：
  • U：向上；
  • D：向下；
  • L：向左；
  • R：向右；
  • ?：未确定；

保证所有 $n\times m$ 之和不超过 $10^6$。

对于每组数据，输出一个整数，表示使得鲁斯塔姆被困住的最多起始单元格数。

翻译：HYdroKomide