NOVICE41 - Verify N queens

no tags 

On a board on size N×N. Johar has placed N stones such that in every row and every column there is exactly one stone. Moreover in every diagonal and anti diagonal there is at most one stone. Now Kandarp want to check his solution because he does not trust Johar. So he want you to check whether he has placed these N stones correctly or not.

Input

First line contains T, the number of test cases. then T test cases follow. First line of each test case contains N (1<=N<=50) then each of next N lines contains an string of N characters. jth character of ith string is '#' is there is an stone at position (i, j) otherwise it is '.'.

Output

For each test case print YES if it is a valid arrangement or NO if it is invalid.

Example

Input:
2
3
..# 
#..
.#.
4
.#..
...#
#...
..#.

Output:
NO
YES

hide comments
Christoph Dürr: 2012-05-14 20:38:19

Beware, the input is malformed. Every line should contain exactly one token (integer or string), but some lines contain more.


Added by:Mahesh Chandra Sharma
Date:2011-03-01
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem