Battleship

2000ms

65536K

Description:

Do you know the game Battleship? If no, look into Wikipedia article http://en.wikipedia.org/wiki/Battleship_(game). You are given the positions of ships on a 10 × 10 board for playing Battleship. According to the rules, the board should contain the following ships:

one of size 4 (4 × 1 or 1 × 4 rectangle),
two of size 3 (3 × 1 or 1 × 3 rectangles),
three of size 2 (2 × 1 or 1 × 2 rectangles),
four of size 1 (1 × 1 rectangles).

The ships should not 'bend', touch each other or overlap in any way. Each ship can be oriented horizontaly or verticaly. Your task is to check whether the given set of boards meets the given conditions.

Input:

The first line contains number n (1 ≤ n ≤ 10) — the number of boards. Each board is described by 10 lines containing 10 characters each. The symbol "0" stands for an empty square and the symbol "*" stands for a square occupied by a ship. The descriptions of boards are separated with empty lines.

Output:

Print n lines YES or NO. Print the first word if the board meets the given conditions; otherwise print the second word.

Sample Input:

Sample Output:

YES
NO

Informação

Provedor Codeforces

Código CF100H