Server Time: Sun Sep 20, 2020 11:52 pm
Welcome ( logout
B - The Crystal Maze
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

You are in a plane and you are about to be dropped with a parasuit in a crystal maze. As the name suggests, the maze is full of crystals. Your task is to collect as many crystals as possible.

To be more exact, the maze can be modeled as an M x N 2D grid where M denotes the number of rows and N denotes the number of columns. There are three types of cells in the grid:

1.      A '#' denotes a wall, you may not pass through it.

2.      A 'C' denotes a crystal. You may move through the cell.

3.      A '.' denotes an empty cell. You may move through the cell.

Now you are given the map of the maze, you want to find where to land such that you can collect maximum number of crystals. So, you are spotting some position x, y and you want to find the maximum number of crystals you may get if you land to cell (x, y). And you can only move vertically or horizontally, but you cannot pass through walls, or you cannot get outside the maze.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing three integers M, N and Q (2 ≤ M, N ≤ 500, 1 ≤ Q ≤ 1000). Each of the next M lines contains N characters denoting the maze. You can assume that the maze follows the above restrictions.

Each of the next Q lines contains two integers xi and yi (1 ≤ xi ≤ M, 1 ≤ yi ≤ N) denoting the cell where you want to land. You can assume that cell (xi, yi) is empty i.e. the cell contains '.'.

Output

For each case, print the case number in a single line. Then print Q lines, where each line should contain the maximum number of crystals you may collect if you land on cell (xi, yi).

Sample Input

Output for Sample Input

1

4 5 2

..#..

.C#C.

##..#

..C#C

1 1

4 1

Case 1:

1

2

Note

Dataset is huge, use faster I/O methods.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan