Path with Sum

You are given a grid with n rows and m columns. Each cell of the grid contains either a 0 or a 1. Starting from the top‐left cell (position (0,0)), you are allowed to move only to the right or down until you reach the bottom‐right cell (position (n-1, m-1)). As you traverse the grid, you accumulate a sum which is defined as the sum of the values in the cells you visit after leaving the starting cell. Your task is to determine if there exists a path whose accumulated sum equals a given target value k.

The allowed moves are described by the following equations in LaTeX format:

\[ (i, j) \to (i, j+1) \quad \text{or} \quad (i, j) \to (i+1, j) \]

If a path exists for which the sum of the encountered values (excluding the starting cell) equals \(k\), you should output YES; otherwise, output NO.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. Each test case begins with a line containing three integers \(n\), \(m\) and \(k\) — the number of rows, the number of columns, and the target sum, respectively. This is followed by \(n\) lines, each containing \(m\) space-separated integers (either 0 or 1) representing the grid.

outputFormat

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

## sample

4
3 3 3
0 1 1
1 0 1
1 1 0
3 3 2
0 1 1
1 0 1
1 1 0
2 2 1
0 1
1 0
2 2 0
0 0
0 0

YES
NO
YES
YES

</p>