Untitled

import java.util.Scanner;

public class Validate {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int tc = scanner.nextInt();
        for (int Case = 1; Case <= tc; Case++) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int[][] arr = new int[n][m];
            boolean[][] check = new boolean[n][m];

            // Input the matrix
            for (int i = 0; i < n; i++) {
                String string = scanner.next();
                for (int j = 0; j < m; j++) {
                    if (string.charAt(j) == '#') {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = 0;
                    }
                    check[i][j] = false;
                }
            }

            // Find a valid path from source to destination
            boolean found = findValidPath(arr, check, n, m);

            if (found) {
                System.out.println("Test Case " + Case + ": Valid");
            } else {
                System.out.println("Test Case " + Case + ": Invalid");
            }
        }
    }

    // Function to find a valid path using DFS
    private static boolean findValidPath(int[][] arr, boolean[][] check, int n, int m) {
        // Find the source and destination points (you need to implement this)
        int sourceRow = 0; // Set to the row of the source point
        int sourceCol = 0; // Set to the column of the source point
        int destRow = n - 1; // Set to the row of the destination point
        int destCol = m - 1; // Set to the column of the destination point

        // Use DFS to find a path from source to destination
        return dfs(arr, check, sourceRow, sourceCol, destRow, destCol);
    }

    // Depth-First Search to find a path
    private static boolean dfs(int[][] arr, boolean[][] check, int currRow, int currCol, int destRow, int destCol) {
        int n = arr.length;
        int m = arr[0].length;

        if (currRow < 0 || currRow >= n || currCol < 0 || currCol >= m || check[currRow][currCol] || arr[currRow][currCol] == 0) {
            return false; // Out of bounds or already visited or blocked cell
        }

        if (currRow == destRow && currCol == destCol) {
            return true; // Found a valid path
        }

        check[currRow][currCol] = true;

        // Explore in all four directions (up, down, left, right)
        if (dfs(arr, check, currRow - 1, currCol, destRow, destCol)
                || dfs(arr, check, currRow + 1, currCol, destRow, destCol)
                || dfs(arr, check, currRow, currCol - 1, destRow, destCol)
                || dfs(arr, check, currRow, currCol + 1, destRow, destCol)) {
            return true;
        }

        return false;
    }
}