Description

There are T tasks you have to solve. In each task, you are given a maze which is a n x m grid. Each cell is marked exactly one character. In the begining, you are at starting point. You need to answer whether it's possible to go to destination. Here are the rules:

1. The cell marked '$' is starting point and the cell marked '&' is destination. There must be exactly one starting point and exactly one destination.
2. The cell marked '#' is wall, you cannot be at that cell.
3. Suppose you are at the cell (i, j), you can go to adjacent cell(i.e (i-1, j), (i, j-1), (i, j+1) and (i+1, j)) if the cell you want to go is not out of bounds and is not marked as '#'.
4. If you are at the cell marked lower case letter, you will be send to the cell marked in corresponding upper case letter. But not vice versa. That is if you are at the cell marked upper case letter, nothing will happen. So you can imagine that they are one-way portal. For every existing lower case letter, there must be exactly one corresponding  upper case letter. And vice versa.

The folloing show how to go to destination for the first and the third task in Sample.

$b.#.                           $a.#.

...#B                           ...#A

...##                           #..#.

##..&                           ...#&

                                .#.#.

-the first task                  -the third task

Note: be carefule of the efficiency of your strategy. 

Input

The first line contains an integer T (1 ≤ T ≤ 10) – the number of tasks you have to solve.

For each task, first there are two integers N, M (2 ≤ N, M ≤ 300) – the gridsize of the maze. Then following N lines contain M characters each, the j-th element in the i-th line S_ij is the character marked for the (i, j) cell(S_ij must be '$' or '&' or '#' or '.' or letter).

Output

For each task output "Yes" if it's possible to go to destination. Otherwise output "No". Then print a newline('\n').

Sample Input  Download

Sample Output  Download

Tags

Discuss