Untitled

package Queue;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

class queue {
	static int[] Data = new int[400];
	static int front, rear;

	public queue() {
		this.front = this.rear = -1;
	}

	void reset() {
		front = rear = -1;
	}

	public void enQueue(int value) {
		Data[++rear] = value;
	}

	int deQueue() {
		return Data[++front];
	}

	boolean isEmpty() {
		if (this.front == this.rear) {
			return true;
		}
		return false;
	}
}

public class Bai4 {

	static int n, m, cnt_exit;
	static char[][] arr = new char[20][20];
	static int[] spinR = { 0, 0, 1, -1 };
	static int[] spinC = { 1, -1, 0, 0 };
	static int cr, cc, nr, nc, r, c;
	static boolean ans = false;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("Text"));
		Scanner scanner = new Scanner(System.in);
		queue rqueue = new queue();
		queue cqueue = new queue();
		int tc = scanner.nextInt();
		for (int Case = 1; Case <= tc; Case++) {
			rqueue.reset();
			cqueue.reset();
			m = scanner.nextInt();
			n = scanner.nextInt();
			for (int i = 0; i < m; i++) {
				String string = scanner.next();
				for (int j = 0; j < n; j++) {
					arr[i][j] = string.charAt(j);
				}
			}
			ans = false;
			cnt_exit = 0;
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
						if (arr[i][j] == '.') {
							cnt_exit++;
							r = i;
							c = j;
						}
					}
				}
			}
			if (cnt_exit == 2) {
				rqueue.reset();
				cqueue.reset();
				rqueue.enQueue(r);
				cqueue.enQueue(c);
			}
			while (rqueue.isEmpty() == false) {
				cr = rqueue.deQueue();
				cc = cqueue.deQueue();
				arr[cr][cc] = 'X';
				for (int i = 0; i < 4; i++) {
					nr = cr + spinR[i];
					nc = cc + spinC[i];
					if (nr >= 0 && nr < m && nc >= 0 && nc < n
							&& arr[nr][nc] == '.') {
						if (nr == 0 | nr == m - 1 || nc == 0 || nc == n - 1) {
							ans = true;
							break;
						}
						rqueue.enQueue(nr);
						cqueue.enQueue(nc);
						arr[nr][nc] = 'X';
					}

				}
				if (ans == true) {
					break;
				}
			}
			if(ans){
				System.out.println(1);
			}else{
				System.out.println(0);
			}

		}
	}
}