Problem: The princess of the Fancy Kingdom has been loved by many people for her lovely face. However the witch of the Snow World has been jealous of the princess being loved. For her jealousy, the witch has shut the princess into the Ice Tower built by the witch’s extreme magical power.

As the Ice Tower is made of cubic ice blocks that stick hardly, the tower can be regarded to be composed of levels each of which is represented by a 2D grid map. The only way for the princess to escape from the tower is to reach downward stairs on every level. However, many magical traps set by the witch obstruct her moving ways. In addition, because of being made of ice, the floor is so slippy that movement of the princess is very restricted. To be precise, the princess can only press on one adjacent wall to move against the wall as the reaction. She is only allowed to move in the vertical or horizontal direction, not in the diagonal direction. Moreover, she is forced to keep moving without changing the direction until she is prevented from further moving by the wall, or she reaches a stairway or a magical trap. She must avoid the traps by any means because her being caught by any of these traps implies her immediate death by its magic. These restriction on her movement makes her escape from the tower impossible, so she would be frozen to death without any help.

You are a servant of the witch of the Snow World, but unlike the witch you love the princess as many other people do. So you decided to help her with her escape. However, if you would go help her directly in the Ice Tower, the witch would notice your act to cause your immediate death along with her. Considering this matter and your ability, all you can do for her is to generate snowmans at arbitrary places (grid cells) neither occupied by the traps nor specified as the cell where the princess is initially placed. These snowmans are equivalent to walls, thus the princess may utilize them for her escape. On the other hand, your magical power is limited, so you should generate the least number of snowmans needed for her escape.

You are required to write a program that solves placement of snowmans for given a map on each level, such that the number of generated snowmans are minimized.



Input

The first line of the input contains a single integer that represents the number of levels in the Ice Tower. Each level is given by a line containing two integers NY (3 ≤ NY ≤ 30) and NX (3 ≤ NX ≤ 30) that indicate the vertical and horizontal sizes of the grid map respectively, and following NY lines that specify the grid map. Each of the NY lines contain NX characters, where ‘A’ represents the initial place of the princess, ‘>’ the downward stairs, ‘.’ a place outside the tower, ‘_’ an ordinary floor, ‘#’ a wall, and ‘^’ a magical trap. Every map has exactly one ‘A’ and one ‘>’.

You may assume that there is no way of the princess moving to places outside the tower or beyond the maps, and every case can be solved with not more than ten snowmans. The judge also guarantees that this problem can be solved without extraordinary optimizations.

Output

For each level, print on a line the least number of snowmans required to be generated for letting the princess get to the downward stairs.

Examples

Input

3
10 30
......#############...........
....##_____________#..........
...#________________####......
..#________####_________#.....
.#________#....##________#....
#_________#......#________#...
#__________###...#_____^^_#...
.#__________A_#...#____^^_#...
..#___________#...#_>__###....
...###########.....####.......
7 17
......#..........
.....#_##........
.#...#_A_#.......
#^####___#.......
#_______#........
#>_____#.........
########.........
6 5
#####
#_A_#
#___#
#_>_#
#___#
#####


Output

2
1
0


Input

3
10 30
......#############...........
....##_____________#..........
...#________________####......
..#________####_________#.....
.#________#....##________#....
_________#......#________#...
__________###...#_____^^_#...
.#__________A_#...#____^^_#...
..#___________#...#_>__###....
...###########.....####.......
7 17
......#..........
.....#_##........
.#...#_A_#.......
^####___#.......
_______#........
>_____#.........
.........
6 5

_A_#
___#
_>_#
___#


Output

2
1
0

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 35

enum DIR{
	North,
	West,
	East,
	South,
	STOP,
};

struct LOC{
	LOC(){

		row = col = 0;
	}
	LOC(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}

	int row,col;
};

int H,W;
LOC start,goal;
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
int back_row[4] = {1,0,0,-1},back_col[4] = {0,1,-1,0};
char base_map[SIZE][SIZE];
bool visited[SIZE][SIZE][5];
bool FLG;
DIR dir[5] = {North,West,East,South,STOP};


bool rangeCheck(LOC loc){

	return loc.row >= 0 && loc.row <= H-1 && loc.col >= 0 && loc.col <= W-1;
}

void init(){

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			for(int i = 0; i < 5; i++){
				visited[row][col][i] = false;
			}
		}
	}
}

bool did_visit(LOC loc){

	for(int i = 0; i < 5; i++){

		if(visited[loc.row][loc.col][dir[i]]){
			return true;
		}
	}

	return false;
}


void recursive(LOC loc,DIR current_dir,int used_num,int max_num){

	if(FLG == true || used_num > max_num)return;

	if(current_dir != STOP){

		LOC next;

		next.row = loc.row+diff_row[current_dir];
		next.col = loc.col+diff_col[current_dir];

		if(rangeCheck(next) == false || base_map[next.row][next.col] == '^')return;


		if(base_map[next.row][next.col] == '#'){ //これ以上進めないので止まらざるを得ない

			if(!visited[loc.row][loc.col][STOP]){

				visited[loc.row][loc.col][STOP] = true;
				recursive(loc,STOP,used_num,max_num);
				visited[loc.row][loc.col][STOP] = false;
			}

		}else if(next.row == goal.row && next.col == goal.col){

			FLG = true; //脱出成功
			return;

		}else{ //mase_map[next.row][next.col] == '_'

			//雪だるまを作らない
			if(!visited[next.row][next.col][current_dir]){
				visited[next.row][next.col][current_dir] = true;
				recursive(next,current_dir,used_num,max_num);
				visited[next.row][next.col][current_dir] = false;
			}

			//雪だるまを作って止まる
			if(used_num < max_num && did_visit(next) == false && visited[loc.row][loc.col][STOP] == false){
				base_map[next.row][next.col] = '#';
				visited[loc.row][loc.col][STOP] = true;
				recursive(loc,STOP,used_num+1,max_num);
				base_map[next.row][next.col] = '_';
				visited[loc.row][loc.col][STOP] = false;
			}
		}

	}else{ //curretn_dir == STOP

		for(int i = 0; i < 4; i++){

			LOC back_pos; //背中にあるセル

			back_pos.row = loc.row+back_row[i];
			back_pos.col = loc.col+back_col[i];

			if(rangeCheck(back_pos) == false)continue; //移動したい方向の背中側に壁が必要

			if(base_map[back_pos.row][back_pos.col] != '#'){
				if(base_map[back_pos.row][back_pos.col] == '_' && used_num < max_num && did_visit(back_pos) == false &&
						current_dir == STOP){ //壁を作って再帰

					base_map[back_pos.row][back_pos.col] = '#';
					recursive(loc,STOP,used_num+1,max_num);
					base_map[back_pos.row][back_pos.col] = '_';
					continue;

				}else{

					continue; //壁を作れないのでSKIP
				}
			}

			LOC next;

			next.row = loc.row+diff_row[i];
			next.col = loc.col+diff_col[i];

			if(rangeCheck(next) == false || base_map[next.row][next.col] == '^')continue;

			if(base_map[next.row][next.col] == '#'){ //これ以上進めないので止まらざるを得ない

				if(visited[loc.row][loc.col][STOP] == false){

					visited[loc.row][loc.col][STOP] = true;
					recursive(loc,STOP,used_num,max_num);
					visited[loc.row][loc.col][STOP] = false;
				}
				continue;
			}

			if(next.row == goal.row && next.col == goal.col){

				FLG = true; //脱出成功
				return;

			}else{ //mase_map[next.row][next.col] == '_'

				//雪だるまを作らない
				if(visited[next.row][next.col][dir[i]] == false){
					visited[next.row][next.col][dir[i]] = true;
					recursive(next,dir[i],used_num,max_num);
					visited[next.row][next.col][dir[i]] = false;
				}

				//雪だるまを作って止まる
				if(used_num < max_num && did_visit(next) == false && visited[loc.row][loc.col][STOP] == false){
					base_map[next.row][next.col] = '#';
					visited[loc.row][loc.col][STOP] = true;
					recursive(loc,STOP,used_num+1,max_num);
					base_map[next.row][next.col] = '_';
					visited[loc.row][loc.col][STOP] = false;
				}
			}

		}
	}
}


bool is_OK(int max_num){

	init();

	FLG = false;
	visited[start.row][start.col][STOP] = true; //同じマスを2度以上通過する場合あり:向きも考慮
	recursive(start,STOP,0,max_num);

	return FLG;
}

void func(){

	scanf("%d %d",&H,&W);

	for(int row = 0; row < H; row++){

		scanf("%s",base_map[row]);
		for(int col = 0; col < W; col++){
			if(base_map[row][col] == 'A'){

				start.row = row;
				start.col = col;
				base_map[row][col] = '_';

			}else if(base_map[row][col] == '>'){

				goal.row = row;
				goal.col = col;
			}
		}
	}

	int ans = 10;

	for(int i = 0; i <= 9; i++){
		if(is_OK(i)){
			ans = i;
			break;
		}
	}

	printf("%d\n",ans);
}

int main(){

	int num_case;
	scanf("%d",&num_case);

	for(int loop = 0; loop < num_case; loop++){

		func();
	}

	return 0;
}