Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 1035
Cube

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Background

After many years of development, Merck has finally discovered a simple model which helps with computer aided drug design. Different chemical substances are viewed as two-dimensional "puzzle" pieces which may be combined in a three-dimensional way, forming more complex structures of atoms. Special combinations of these pieces have very special chemical properties. These combinations which are known as ACM (Anachronistic Cube Molecules) result from combining six individual puzzle pieces along their edges to form a complete cube (see Figure 3).

Figure 3: Construction of a cube.

Problem

Given six pieces, decide whether they can be put together to form a cube of dimension 6 * 6 * 6, with no holes visible from the outside. Each piece can be thought of as being cut from a plate of wood of dimension 6 * 6 * 1, with the 4 * 4 * 1 plate in the centre untouched. A piece can be used the one or the other way around, i.e., there is no distinction between the inside and the outside.

Input

The first line contains the number of scenarios.

In each scenario, you are first given six lines with a graphical representation of the six pieces. In that representation, "X" symbolises solid wood, a dot "." stands for a 1 * 1 * 1 piece of wood that was cut out. A column with "!" stands on the right of each piece to separate them from each other. There is a blank line following every scenario.

It is not necessary that the pieces can really be cut out of wood or that they form a stable cube, as you can see in the sample input, second example.

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. In the next line print "Yes" or "No" depending on whether the given pieces can be put together to form a cube. Terminate the output for the scenario with a blank line.

Sample Input

```3
XX..XX!.X..X.!XX..XX!.X..X.!..XX..!..XX..!
XXXXXX!.XXXX.!XXXXXX!.XXXX.!.XXXX.!.XXXX.!
.XXXX.!XXXXXX!.XXXX.!XXXXXX!XXXXXX!XXXXXX!
.XXXX.!XXXXXX!.XXXX.!XXXXXX!XXXXXX!XXXXXX!
XXXXXX!.XXXX.!XXXXXX!.XXXX.!.XXXX.!.XXXX.!
XX..XX!.X..X.!XX..XX!.X..X.!..XX..!..XX..!

.XXXX.!.XXXX.!.XXXX.!.XXXX.!XXXXXX!X....X!
XXXXXX!.XXXX.!XXXXXX!.XXXX.!XXXXXX!.XXXX.!
XXXXXX!.XXXX.!XXXXXX!.XXXX.!XXXXXX!.XXXX.!
XXXXXX!.XXXX.!XXXXXX!.XXXX.!XXXXXX!.XXXX.!
XXXXXX!.XXXX.!XXXXXX!.XXXX.!XXXXXX!.XXXX.!
......!......!......!......!XXXXXX!X....X!

......!......!......!......!......!......!
.XXXX.!.XXXX.!.XXXX.!.XXXX.!.XXXX.!.XXXX.!
.XXXX.!.XXXX.!.XXXX.!.XXXX.!.XXXX.!.XXXX.!
.XXXX.!.XXXX.!.XXXX.!.XXXX.!.XXXX.!.XXXX.!
.XXXX.!.XXXX.!.XXXX.!.XXXX.!.XXXX.!.XXXX.!
......!......!......!......!......!......!
```

Sample Output

```Scenario #1:
Yes

Scenario #2:
Yes

Scenario #3:
No

```

Source: Northwestern Europe 2001
Submit    Status