Cake Partitioning with Strawberries

You are given a cake represented as a grid of size \(M \times N\). Each cell is either empty (denoted by .) or contains a strawberry (denoted by S). Your task is to determine whether it is possible to cut the cake into exactly \(K\) pieces such that no piece contains more than one strawberry.

The cake can only be cut along the grid lines, dividing it into contiguous rectangular pieces. Note the following:

• If there are no strawberries, the cake can always be cut into \(K\) pieces.
• If the number of strawberries is greater than \(K\), it is impossible to isolate each strawberry into a separate piece.
• If there is exactly one strawberry, then as long as \(K \ge 1\) the answer is "YES".
• In other cases, by counting the number of possible cuts along rows and columns that can isolate strawberries, one can decide whether the cake can be partitioned under the rules.

Determine if it is possible to perform such a partition.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Each test case is described as follows:

1. A line containing three integers \(M\), \(N\), and \(K\), where \(M\) is the number of rows, \(N\) is the number of columns, and \(K\) is the required number of pieces.
2. Then follow \(M\) lines, each containing a string of length \(N\) representing the cake. The character S indicates a strawberry, and . indicates an empty cell.

Read from standard input (stdin).

outputFormat

For each test case, output a single line containing either YES if the cake can be partitioned according to the requirements, or NO if it cannot.

Write to standard output (stdout).

## sample

3
3 3 4
...
.S.
...
5 5 5
.....
...S.
.....
.S...
.....
4 4 2
.S..
..S.
....
....

YES
NO
NO

</p>