Cubic Rube

Time limit1sMemory limit128 MB

Summary
Given two connected 5x5 height maps of unit cubes, decide whether the pieces can be rotated and translated in 3D to assemble a full 5x5x5 cube.
Level

Hard9 of 10

Topics
Implementation, Geometry, Brute force, Sorting
Solved
No attempts yet

Problem

You work in a Rubik's Cube factory and are designing a new variation: a 5×5×55\times5\times5 Rubik's Cube. Your only working prototype fell to the floor and broke into exactly two pieces. You are holding one piece and must decide whether a second piece can complete it.

Each piece is a solid made of unit cubes. Given the two pieces, determine whether they can be fitted together — using rotations and translations in 3D space — to form a solid 5×5×55\times5\times5 cube with no gaps and no overlaps.

Input

The first line contains an integer nn, the number of data sets.

Each data set is given on the next 5 lines. Each line contains two 5-character strings separated by a single space; the left string describes the first solid and the right string describes the second solid. Together the 5 lines give a top-down (bird's-eye) view of each solid as a 5×55\times5 grid of digits 0–9.

Each digit is the height of that solid at that grid point (the number of unit cubes stacked there). A height of 0 means no cube is present at that point. This is a topographic map: assume there are no hidden gaps underneath any visible part, so a column of height hh is a solid stack of hh unit cubes.

Each solid is a single connected piece, and joining the two solids may require translations, not only rotations.

Output

For each data set, print Yes on its own line if the two solids can be fitted together to form a solid 5×5×55\times5\times5 cube, or No otherwise.

Examples1

  1. Example 1

    Input
    2
    55551 11111
    55551 11111
    55551 11111
    55551 11110
    55552 00000
    22222 33333
    22222 33333
    22222 33233
    22222 33333
    22222 33333
    
    Expected output
    Yes
    No