Minimum Moves to Collect Resources

Given an integer \(Q\) representing the number of queries, process each query independently. For each query you are given a grid with \(R\) rows and \(C\) columns, and two integers \(K\) and \(T\). Each cell of the grid contains an integer. You can start from any cell that contains the resource value \(T\). When you start, you already collect the resource from the starting cell. From there, you can move in the four cardinal directions (up, down, left, right), but you cannot visit any cell more than once in the same query. Each move increases the move count by 1, and if you enter a cell containing \(T\), you collect that resource. Your goal is to collect exactly \(K\) resources (including the starting cell). If it is possible, output the minimum number of moves required; otherwise, output -1.

Note: The moves are counted as the number of transitions between the cells. The initial cell (starting position) does not count as a move.

Input and output are handled via standard input and output respectively.

inputFormat

The input begins with an integer \(Q\) representing the number of queries. For each query:

1. The first line contains four space-separated integers: \(R\), \(C\), \(K\), and \(T\).
2. The next \(R\) lines each contain \(C\) space-separated integers representing the grid.

outputFormat

For each query, output a single integer on a new line representing the minimum number of moves required to collect exactly \(K\) resources. If it is impossible, output -1.

## sample

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

2
4
-1

</p>