Ivan 有一个大小为 $2^k \times 2^{k+1}$ 的方格矩形，他想将其分割成多米诺骨牌（大小为 $1 \times 2$ 或 $2 \times 1$ 的矩形）。

为了实现这一点，他开发了以下递归算法：

• 如果 $k = 0$，则矩形大小为 $1 \times 2$，分割完成。
• 否则，将矩形视为由大小为 $2^{k-1} \times 2^{k-1}$ 的大单元格组成的 $2 \times 4$ 矩形。将其分割成多米诺骨牌有 5 种可能的方式（见下文）。选择其中一种分割方式。所得的碎片大小将为 $2^{k-1} \times 2^k$ 或 $2^k \times 2^{k-1}$。对每一个碎片递归地进行分割。

Ivan 非常喜欢他的生成器。它可以生成许多非平凡的多米诺骨牌平铺方案。他生成了一些平铺方案并将其保存在电脑上的文件中。不幸的是，电脑损坏了，关于平铺方案中一些多米诺骨牌的信息丢失了。

给定 $2^k \times 2^{k+1}$ 矩形中一些互不重叠的多米诺骨牌。关于未被多米诺骨牌覆盖的单元格的信息已丢失。请找出有多少种不同的平铺方案可以由上述算法生成，且满足所有给定的多米诺骨牌都存在于平铺方案中。

更正式地说，如果存在一种在每一步分割 $2 \times 4$ 矩形的方式，使得最终的平铺方案符合要求，则该平铺方案可以由算法生成。如果两个平铺方案中的多米诺骨牌集合不同，则认为它们是不同的。

由于不同平铺方案的数量可能很大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $k$ ($0 \le k \le 10$)。

接下来的 $2^k$ 行描述了棋盘的平铺情况，按从上到下的顺序。每一行包含 $2^{k+1}$ 个字符，描述了对应行从左到右的单元格。每个字符为 ‘U’、‘D’、‘L’、‘R’ 或 ‘.’，分别表示该单元格被多米诺骨牌的上半部分、下半部分、左半部分、右半部分覆盖，或未被覆盖。

保证所有测试用例的 $4^k$ 之和不超过 $2^{20}$。

输出格式

对于每个测试用例，输出一个整数，表示可以由算法生成的不同平铺方案的数量，对 $998\,244\,353$ 取模。

样例

输入格式 1

5
0
..
1
...U
...D
2
.UU.LRUU
.DD...DD
.ULR...U
.D..LR.D
2
.LR.....
U.......
D.......
........
3
LRLR.....ULR....
.U.......D..LR..
.D.......ULR....
LRLR.....D......
....LRLR....LRLR
....U.......U...
....D.......D...
....LRLR....LRLR

输出格式 1

1
3
2
0
7657344

说明

第三个测试用例的一种可能平铺方案如下图所示：