#P12097. [NERC2024] Fix Flooded Floor

[NERC2024] Fix Flooded Floor

Description

阿基米德进行了他的著名浮力实验。但是少有人知道,他洗澡时太过专注,没有注意到水从浴缸边溢出,使他的木地板发生了不可逆的破坏。

阿基米德发现,并非所有地板都损坏了,还剩下一些地板是完好的。墙边的木地板区域形状为 2×n2 \times n 的长条带。阿基米德有无限多的 1×21 \times 2 地板块,它们可以平行或垂直于墙壁放置。阿基米德不想分割这些板块。作为伟大的科学家,他知道了恰好存在一种通过使用不重叠的 1×21 \times 2 地板块修复损坏区域的方式。

帮助历史学家检查阿基米德的演算,对于给定的 2×n2 \times n 的木地板,判断是否恰好存在一种方法,使得可以用 1×21 \times 2 地板块修复损坏区域。如果他的结果错了,请回答是存在多种修复方式还是不存在方式。

Input Format

第一行包括一个整数 TT (1T1041 \le T \le 10^4),表示测试用例的数量。

之后是测试用例的描述。

每个测试用例的第一行包括一个整数 nn (1n21051 \le n \le 2 \cdot 10^5),表示木地板的长度。

接下来的两行各有 nn 个字符,表示木地板的状态,其中 .\texttt{.} 表示损坏的区域,#\texttt{\#} 表示完好的区域。

总共 TT 个测试用例中 n\sum n 不超过 21052 \cdot 10^5

Output Format

对于每个测试用例,若恰好存在一种修复的方式,输出 Unique\tt{Unique};,若存在多种方式,输出 Mutiple\tt{Mutiple};若无法修复,输出 None\tt{None}

4
10
#.......##
##..#.##..
6
...#..
..#...
8
........
........
3
###
###
Unique
None
Multiple
Unique