Maximum Gems Collection in a Grid

You are given a grid with n rows and m columns. Each cell of the grid can either be:

• A `.` representing an empty space,
• A `#` representing an obstacle, or
• A `G` representing a gem.

A character starts at position \( (r, c) \) (1-indexed) and can move up, down, left, or right. The character collects a gem immediately when stepping into a cell containing a gem, and that cell then becomes empty. However, the character can collect at most \( g \) gems in total. The task is to compute the maximum number of gems that the character can collect by exploring the grid using a breadth-first search approach.

Note: The movement is only allowed into cells that are not obstacles, and once the maximum allowed gems are collected, the search stops.

The formula for the maximum number of gems collected can be thought as:

\[ \text{Result} = \min\left(\text{number of reachable gems}, g\right) \]

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n m r c g
row1
row2
...
rown
... (This repeats for T test cases)

</p>

Here, T is the number of test cases. For each test case:

• \( n \) and \( m \) represent the dimensions of the grid.
• \( r \) and \( c \) are the starting row and column (1-indexed).
• \( g \) is the maximum number of gems the character can collect.
• Each of the next \( n \) lines contains a string of length \( m \) representing a row of the grid.

outputFormat

For each test case, output a single line containing the maximum number of gems the character can collect. The output is printed to standard output (stdout).

## sample

5
5 5 3 3 2
.....
..G..
..#..
.###.
.....
4 4 2 2 3
..G.
.#G.
..G.
....
5 5 1 1 2
.....
...#.
..G..
.##..
.....
5 5 4 1 2
#.#..
G#G..
#.#G.
.....
...G#
1 1 1 1 1
G

1
3
1
2
1

</p>