홍수 난 바닥 고치기
면접 대비시간 제한3초메모리 제한2048 MB
2xn 격자에서 '#'은 막힌 칸, '.'은 빈 칸일 때, 빈 칸을 1x2 조각으로 채우는 방법이 하나인지, 여러 개인지, 없는지 판별합니다.
문제
아르키메데스는 부력에 관한 유명한 실험을 했다. 그런데 목욕을 하던 중 생각에 너무 몰두한 나머지, 물이 욕조 가장자리를 넘쳐 벽 근처 바닥을 적시는 순간을 알아차리지 못했다. 그 바람에 값비싼 마루(파케이)가 돌이킬 수 없이 손상되었다!
그래도 모든 것이 잃어버린 것은 아니었다. 손상되지 않은 마루 조각이 아직 여러 개 남아 있었다. 벽 근처의 마루는 길고 좁은 칸짜리 띠 모양이었다. 아르키메데스에게는 벽과 평행하게 또는 수직으로 놓을 수 있는 크기의 마루 조각이 무한히 있었다. 그는 조각을 자르고 싶지 않았다. 위대한 과학자답게, 그는 손상된 부분을 겹치지 않는 칸 조각으로 채우면 마루를 복원하는 방법이 정확히 하나뿐이라는 것을 계산해 냈다.
역사학자들이 아르키메데스의 계산을 검증하도록 도와라. 주어진 마루 배치에서, 손상된 칸을 조각으로 채우는 방법이 정확히 하나인지 판단하라. 아르키메데스가 틀렸다면, 복원 방법이 여러 개인지 아니면 방법이 아예 없는지 알아내라.
입력
첫 줄에 테스트 케이스의 수 ()가 주어진다. 이후 각 테스트 케이스가 이어진다.
각 테스트 케이스의 첫 줄에는 마루의 길이 ()이 주어진다. 다음 두 줄에는 각각 정확히 글자로 마루의 상태가 주어진다. .은 손상된 칸, #은 손상되지 않은 칸을 뜻한다.
모든 테스트 케이스의 합은 을 넘지 않는다.
출력
각 테스트 케이스마다 마루를 복원하는 방법이 정확히 하나이면 Unique, 여러 개이면 Multiple, 복원이 불가능하면 None을 출력한다.