B. Make Connected
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an $$$n \times n$$$ grid where some cells are colored black, and the rest are white. You may paint some of the white cells black to achieve the following conditions:

  1. There is at least one black cell.
  2. All black cells must be orthogonally connected, that is, it should be possible to go from any black cell to any other by crossing several vertical or horizontal cell borders while visiting only black cells. You can't go directly through the corner of a cell.
  3. There are no three consecutive black cells aligned vertically or horizontally.

You can't paint black cells white.

Determine whether it is possible to paint some white cells black in order to satisfy all the conditions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the size of the grid.

The following $$$n$$$ lines contain $$$n$$$ characters each — the grid description, where each character represents a cell:

  • . — a white cell;
  • # — a black cell.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, print "YES" if it is possible to paint some white cells black to satisfy all the conditions, and "NO" otherwise.

You may print each letter in any case (uppercase or lowercase). For example, the strings "yEs", "yes", "Yes", and "YES" will all be recognized as a positive answer.

Example
Input
11
1
.
1
#
3
.##
.##
...
3
#..
.#.
..#
3
###
...
...
3
#.#
...
.#.
4
####
#..#
#..#
####
3
..#
...
.#.
3
..#
#..
...
5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#
5
...#.
...#.
.....
##...
.....
Output
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
YES
Note

In the first test case, there are no black cells, so we must paint one cell black.

In the second and third test cases, the grid satisfies all the conditions from the very beginning.

In the fourth test case, one of the possible solutions is:

##.
.##
..#

In the fifth test case, the grid violates the "No three consecutive black cells should be aligned vertically or horizontally" condition from the very beginning, so there is no solution.

In the sixth test case, it can be shown that it is impossible to achieve a connected grid without violating the condition about three consecutive black cells.