Problem: Vivek has encountered a problem. He has a maze that can be represented as an n × m grid. Each of the grid cells may represent the following:

  * Empty — '.' 
  * Wall — '#' 
  * Good person — 'G' 
  * Bad person — 'B' 



The only escape from the maze is at cell (n, m).

A person can move to a cell only if it shares a side with their current cell and does not contain a wall. Vivek wants to block some of the empty cells by replacing them with walls in such a way, that all the good people are able to escape, while none of the bad people are able to. A cell that initially contains 'G' or 'B' cannot be blocked and can be travelled through.

Help him determine if there exists a way to replace some (zero or more) empty cells with walls to satisfy the above conditions.

It is guaranteed that the cell (n,m) is empty. Vivek can also block this cell.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n, m (1 ≤ n, m ≤ 50) — the number of rows and columns in the maze.

Each of the next n lines contain m characters. They describe the layout of the maze. If a character on a line equals '.', the corresponding cell is empty. If it equals '#', the cell has a wall. 'G' corresponds to a good person and 'B' corresponds to a bad person.

Output

For each test case, print "Yes" if there exists a way to replace some empty cells with walls to satisfy the given conditions. Otherwise print "No"

You may print every letter in any case (upper or lower).

Example

Input


6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#..
GG.
2 2
#B
B.


Output


Yes
Yes
No
No
Yes
Yes

Note

For the first and second test cases, all conditions are already satisfied.

For the third test case, there is only one empty cell (2,2), and if it is replaced with a wall then the good person at (1,2) will not be able to escape.

For the fourth test case, the good person at (1,1) cannot escape.

For the fifth test case, Vivek can block the cells (2,3) and (2,2).

For the last test case, Vivek can block the destination cell (2, 2).

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
public class D648 {

	public static int[] dx = {0, 1, 0, -1};
	public static int[] dy = {1, 0, -1, 0};
	
	public static void main(String[] args) {
		FastScanner in = new FastScanner(System.in);
		int T = in.nextInt();
		StringBuilder sb = new StringBuilder();
		
		while(T --> 0) {
			int N = in.nextInt();
			int M = in.nextInt();
			
			char[][] board = new char[N][M];
			
			for(int i = 0; i <N ; i++) {
				String g = in.next();
				
				for(int j = 0; j < M; j++) {
					char c = g.charAt(j);
					board[i][j] = c;
					
				}
				
				
			}
			
			boolean b = ans(N, M, board);
			if(b) {
				System.out.println("Yes");
			}
			else {
				System.out.println("No");
			}
			
			
		}
		
		System.out.print(sb);

	}
	
	public static boolean valid(int x, int y, int N, int M) {
		return (0 <= x && x < N && 0 <= y && y < M);
	}
	
	public static boolean ans(int N, int M, char[][] board) {
		int numGood = 0;
		int numBad = 0;
		
		for(int i = 0; i <N ; i++) {
			for(int j = 0; j < M; j++) {
				char c= board[i][j];
				if(c == 'G') {
					numGood++;
				}
				else if(c == 'B') {
					numBad++;
				}
				
			}
		}
		
		
		if(numGood == 0) {
			return true;
		}
		
		
		
		UF uf = new UF(N * M);
		for(int i = 0; i <N ; i++) {
			for(int j = 0; j < M; j++) {
				char ch= board[i][j];
				if(ch != '#') {
					for(int k = 0; k < 4; k++ ) {
						int r = i + dx[k];
						int c = j + dy[k];
						
						if(valid(r, c, N, M) && board[r][c] != '#') {
							int num1 = M * i + j;
							int num2 = M * r + c;
							
							uf.union(num1, num2);
						}
					}
				}
			}
		}
		
		boolean traversable = true;
		
		for(int i = 0; i <N ; i++) {
			for(int j = 0; j < M; j++) {
				char ch = board[i][j];
				if(ch == 'G') {
					int num1 = M * i + j;
					
					int num2 = M * (N - 1) + M - 1;
					
					
					boolean b = uf.connected(num1, num2);
					if(!b) {
						traversable = false;
						break;
					}
				}
				
			}
			
		}
		
		if(!traversable) {
			return false;
		}
		
		for(int i = 0; i < N ; i++) {
			for(int j = 0; j < M; j++) {
				char ch= board[i][j];
				if(ch == 'B') {
					for(int k = 0; k < 4; k++) {
						int r = i + dx[k];
						int c = j + dy[k];
						
						if(valid(r, c, N, M) && board[r][c] == '.') {
							//int num1 = M * i + j;
							
							board[r][c] = '#';
						}
					}
					
				}
				
			}
			
		}
		
		uf = new UF(N * M);
		
		for(int i = 0; i <N ; i++) {
			for(int j = 0; j < M; j++) {
				char ch= board[i][j];
				if(ch != '#') {
					for(int k = 0; k < 4; k++ ) {
						int r = i + dx[k];
						int c = j + dy[k];
						
						if(valid(r, c, N, M) && board[r][c] != '#') {
							int num1 = M * i + j;
							int num2 = M * r + c;
							
							uf.union(num1, num2);
						}
					}
				}
			}
		}
		
		traversable = true;
		
		for(int i = 0; i <N ; i++) {
			for(int j = 0; j < M; j++) {
				char ch= board[i][j];
				if(ch == 'G') {
					int num1 = M * i + j;
					
					int num2 = M * (N - 1) + M - 1;
					
					
					boolean b = uf.connected(num1, num2);
					if(!b) {
						traversable = false;
						break;
					}
				}
				
			}
			
		}
		
		
		if(!traversable) {
			return false;
		}
		
		
		traversable = false;
		for(int i = 0; i <N ; i++) {
			for(int j = 0; j < M; j++) {
				char ch= board[i][j];
				if(ch == 'B') {
					int num1 = M * i + j;
					
					int num2 = M * (N - 1) + M - 1;
					
					
					boolean b = uf.connected(num1, num2);
					if(b) {
						traversable = true;
						break;
					}
				}
				
			}
			
		}
		
		if(traversable) {
			return false;
		}
		
		return true;
		
	}
	
	
	static class Pair implements Comparable<Pair> {
		int a;
		int b;

		public Pair(int x, int y) {
			a = x;
			b = y;
		}

		public int compareTo(Pair p2) {
			if (a < p2.a)
				return -1;
			if (a == p2.a) {
				if (b < p2.b)
					return -1;
				if (b == p2.b)
					return 0;
				return 1;
			}
			return 1;
		}

		public boolean equals(Object o) {
			if (!(o instanceof Pair))
				return false;
			Pair p2 = (Pair) o;
			return (a == p2.a && b == p2.b);
		}

		public int hashCode() {
			return (a + " " + b).hashCode();
		}

		public String toString() {
			return "(" + a + ", " + b + ")";
		}
	}
	
	/**
	 *  The {@code UF} class represents a <em>union�find data type</em>
	 *  (also known as the <em>disjoint-sets data type</em>).
	 *  It supports the classic <em>union</em> and <em>find</em> operations,
	 *  along with a <em>count</em> operation that returns the total number
	 *  of sets.
	 *  <p>
	 *  The union�find data type models a collection of sets containing
	 *  <em>n</em> elements, with each element in exactly one set.
	 *  The elements are named 0 through <em>n</em>�1.
	 *  Initially, there are <em>n</em> sets, with each element in its
	 *  own set. The <em>canonical element</em> of a set
	 *  (also known as the <em>root</em>, <em>identifier</em>,
	 *  <em>leader</em>, or <em>set representative</em>)
	 *  is one distinguished element in the set. Here is a summary of
	 *  the operations:
	 *  <ul>
	 *  <li><em>find</em>(<em>p</em>) returns the canonical element
	 *      of the set containing <em>p</em>. The <em>find</em> operation
	 *      returns the same value for two elements if and only if
	 *      they are in the same set.
	 *  <li><em>union</em>(<em>p</em>, <em>q</em>) merges the set
	 *      containing element <em>p</em> with the set containing
	 *      element <em>q</em>. That is, if <em>p</em> and <em>q</em>
	 *      are in different sets, replace these two sets
	 *      with a new set that is the union of the two.
	 *  <li><em>count</em>() returns the number of sets.
	 *  </ul>
	 *  <p>
	 *  The canonical element of a set can change only when the set
	 *  itself changes during a call to <em>union</em>&mdash;it cannot
	 *  change during a call to either <em>find</em> or <em>count</em>.
	 *  <p>
	 *  This implementation uses <em>weighted quick union by rank</em>
	 *  with <em>path compression by halving</em>.
	 *  The constructor takes &Theta;(<em>n</em>) time, where
	 *  <em>n</em> is the number of elements.
	 *  The <em>union</em> and <em>find</em> operations take
	 *  &Theta;(log <em>n</em>) time in the worst case.
	 *  The <em>count</em> operation takes &Theta;(1) time.
	 *  Moreover, starting from an empty data structure with <em>n</em> sites,
	 *  any intermixed sequence of <em>m</em> <em>union</em> and <em>find</em>
	 *  operations takes <em>O</em>(<em>m</em> &alpha;(<em>n</em>)) time,
	 *  where &alpha;(<em>n</em>) is the inverse of
	 *  <a href = "https://en.wikipedia.org/wiki/Ackermann_function#Inverse">Ackermann's function</a>.
	 *  <p>
	 *  For alternative implementations of the same API, see
	 *  {@link QuickUnionUF}, {@link QuickFindUF}, and {@link WeightedQuickUnionUF}.
	 *  For additional documentation, see
	 *  <a href="https://algs4.cs.princeton.edu/15uf">Section 1.5</a> of
	 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
	 *
	 *  @author Robert Sedgewick
	 *  @author Kevin Wayne
	 */

	public static class UF {

	    private int[] parent;  // parent[i] = parent of i
	    private byte[] rank;   // rank[i] = rank of subtree rooted at i (never more than 31)
	    private int count;     // number of components

	    /**
	     * Initializes an empty union-find data structure with
	     * {@code n} elements {@code 0} through {@code n-1}.
	     * Initially, each elements is in its own set.
	     *
	     * @param  n the number of elements
	     * @throws IllegalArgumentException if {@code n < 0}
	     */
	    public UF(int n) {
	        if (n < 0) throw new IllegalArgumentException();
	        count = n;
	        parent = new int[n];
	        rank = new byte[n];
	        for (int i = 0; i < n; i++) {
	            parent[i] = i;
	            rank[i] = 0;
	        }
	    }

	    /**
	     * Returns the canonical element of the set containing element {@code p}.
	     *
	     * @param  p an element
	     * @return the canonical element of the set containing {@code p}
	     * @throws IllegalArgumentException unless {@code 0 <= p < n}
	     */
	    public int find(int p) {
	        validate(p);
	        while (p != parent[p]) {
	            parent[p] = parent[parent[p]];    // path compression by halving
	            p = parent[p];
	        }
	        return p;
	    }

	    /**
	     * Returns the number of sets.
	     *
	     * @return the number of sets (between {@code 1} and {@code n})
	     */
	    public int count() {
	        return count;
	    }
	  
	    /**
	     * Returns true if the two elements are in the same set.
	     *
	     * @param  p one element
	     * @param  q the other element
	     * @return {@code true} if {@code p} and {@code q} are in the same set;
	     *         {@code false} otherwise
	     * @throws IllegalArgumentException unless
	     *         both {@code 0 <= p < n} and {@code 0 <= q < n}
	     */
	    public boolean connected(int p, int q) {
	        return find(p) == find(q);
	    }
	  
	    /**
	     * Merges the set containing element {@code p} with the 
	     * the set containing element {@code q}.
	     *
	     * @param  p one element
	     * @param  q the other element
	     * @throws IllegalArgumentException unless
	     *         both {@code 0 <= p < n} and {@code 0 <= q < n}
	     */
	    public void union(int p, int q) {
	        int rootP = find(p);
	        int rootQ = find(q);
	        if (rootP == rootQ) return;

	        // make root of smaller rank point to root of larger rank
	        if      (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
	        else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
	        else {
	            parent[rootQ] = rootP;
	            rank[rootP]++;
	        }
	        count--;
	    }

	    // validate that p is a valid index
	    private void validate(int p) {
	        int n = parent.length;
	        if (p < 0 || p >= n) {
	            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));  
	        }
	    }

	}

	
	/**
	 * Source: Matt Fontaine
	 */
	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int chars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
		}

		int read() {
			if (chars == -1)
				throw new InputMismatchException();
			if (curChar >= chars) {
				curChar = 0;
				try {
					chars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (chars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}

}
/*
6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#..
GG.
2 2
#B
B.
outputCopy
Yes
Yes
No
No
Yes
Yes


1
1 3
BG.

No
*/