Under construction

Still being built. Things may change

Fix Flooded Floor

Interview

Time limit3sMemory limit2048 MB

Summary
Given a 2xn grid where '#' marks blocked cells and '.' marks empty cells, decide if the empty cells have exactly one, multiple, or no tilings with 1x2 dominoes.
Level

Medium5 of 10

Topics
Dynamic programming, Implementation
Solved
No attempts yet

Statement

Archimedes conducted his famous experiments on buoyancy. But not everyone knows that while he was taking a bath, he was too focused and didn't notice the moment when the water overflowed over the edge of the bath and flooded the floor near the wall. His expensive parquet was irreversibly damaged!

Archimedes noticed that not all was lost, and there were still several undamaged parquet pieces. The parquet near the wall had the shape of a long narrow stripe of 2×n2\times n cells. Archimedes had an unlimited supply of 1×21\times 2 parquet pieces that could be placed parallel or perpendicular to the wall. Archimedes didn't want to cut the parquet pieces. As a great scientist, he figured out that there was exactly one way to restore the parquet by filling the damaged area of the parquet with the non-overlapping 1×21\times 2 cell shaped pieces.

Help historians check Archimedes' calculations. For the given configuration of the 2×n2\times n parquet floor, determine whether there is exactly one way to fill the damaged parquet cells with the 1×21\times 2 cell parquet pieces. If Archimedes was wrong, find out whether there are multiple ways to restore the parquet, or whether there are no ways at all.

Input

The first line contains a single integer TT (1≤T≤1041 \le T \le 10^4), the number of test cases to solve. Then the description of test cases follows.

The first line of each test case contains a single integer nn (1≤n≤2⋅1051 \le n \le 2\cdot 10^5), the length of the parquet floor. The following two lines contain exactly nn characters each and describe the parquet, where . denotes a damaged cell and # denotes an undamaged cell.

The total sum of nn in all test cases doesn't exceed 2⋅1052\cdot 10^5.

Output

For each test case, print Unique if there is exactly one way to restore the parquet, Multiple if there are multiple ways to do so, or None if it is impossible to restore the parquet.

Examples1

  1. Example 1

    Input
    4
    10
    #.......##
    ##..#.##..
    6
    ...#..
    ..#...
    8
    ........
    ........
    3
    ###
    ###
    
    Expected output
    Unique
    None
    Multiple
    Unique