Romantic King

A king dearly loves his queen. One day, he prepares a surprise party to make her happy, but just a few hours before the party he realizes that he forgot to prepare a gift.

Fortunately, gift trees grow around the city where the king and queen live. The king wants to bring as many gifts as possible, but he never exercises, so every gift he carries slows him down.

The king starts at K and must finish at the queen's castle Q within the given time. He normally moves one grid cell in 1 hour. If he is carrying q gifts, moving one grid cell takes q + 1 hours. Each gift tree G can provide one gift. The king may pass through the queen's cell while going to collect more gifts, but the trip only ends when he finally decides to arrive there.

Find the maximum number of gifts the king can deliver to the queen.

The first line contains the number of test cases T.

For each test case, one line contains the city's height, width, and the available time. The next height lines describe the city map.

The map characters are:

• Q: the queen's castle
• K: the king's starting position
• G: a gift tree
• .: a road
• #: a blocked cell

The height and width are each between 1 and 50, inclusive. Each city has between 0 and 16 gift trees. The input always guarantees that the king can reach the queen.

For each test case, output the maximum number of gifts the king can bring to the queen.