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