Path Finding with Exactly K Empty Cells

You are given a board represented by an N x M grid. Each cell is either an empty cell represented by a dot ('.') or an obstacle represented by a hash ('#'). Your task is to determine if there exists a path that passes through exactly \(K\) empty cells.

The path can start from any empty cell and moves to adjacent cells in the four cardinal directions (up, down, left, right). A cell cannot be visited more than once in a single path. If such a path exists, print "YES"; otherwise, print "NO".

Note: The number \(K\) includes the starting cell.

inputFormat

The first line contains an integer \(T\) (the number of test cases). For each test case:

• The first line contains three integers \(N\), \(M\), and \(K\).
• The next \(N\) lines each contain a string of \(M\) characters representing the board.

It is guaranteed that \(N, M\) and \(K\) are such that a solution using DFS/backtracking will run within the time limits.

outputFormat

For each test case, output a single line containing "YES" if a valid path exists, otherwise "NO".

## sample

2
4 4 4
...#
.#..
....
#.##
3 3 6
##.
.#.
##.

YES
NO

</p>