ACM-ICPC Indonesia National Contest 2014

Problem D

Breaking Board

Time Limit: 2 seconds

There are two types of coordinate in a board of size R x C: grid-coordinate and cell-coordinate. Usually we do not care about this coordinate system, but as we are going to use both system in this problem, we need to make convention about the coordinate system. Grid-coordinate determines the position of each point (line intersection) on the board, starting from (0,0) at top-left most up to (R,C) at bottom-right most of the board. On the other hand, cell-coordinate determines the position of each cell (area bounded by 2 adjacent vertical lines and 2 adjacent horizontal lines) on the board, starting from (1,1) at top-left most up to (R,C) at bottom-right most of the board. To differentiate these two coordinate system, we will refer grid-coordinate as g(row,col) and cell-coordinate as c(row,col). For example, g(2,1) corresponds to the point created by intersection of the 3rd horizontal line from the top and the 2nd vertical line from the left; c(2,3) corresponds to cell/area bounded by the 2nd and 3rd horizontal lines from the top and 3rd and 4th vertical lines from the left. See Figure 1 for clarity.


Figure 1. Coordinate system of a board. g(row,col) corresponds to
grid-coordinate, while c(row,col) corresponds to cell-coordinate.

In this problem, you're given a board of size R x C and N coins. Each coin has a mark (either X or O) on it, and located in one of the cell on the board. You have to divide the board into two parts by the following rule: starting from g(0,0), draw a line along the grid either to the right or down direction, until you reach g(R,C). This division will break the board into exactly two parts. Let A and B be the collection of coins on each of the broken board. You are allowed to swap coins in A with coins in B, and your goal is to make all coins in both collections have the same mark with other coins in the same collection. See Figure 2 for example.


Figure 2. Breaking board example.

Solution #1 in Figure 2 is one way to break the board into two parts. Using solution #1, we will get A = {O, X} and B = {X}, thus we need to swap one O in A with one X in B to obtain A = {X, X} and B = {O}. Solution #1 requires 1 swap to achive the goal. Solution #2, on the other hand, does not require any swap to achive the goal, and A = {O}, B = {X, X}. Of course, there exists other solutions which do not require swap to achieve the goal in this example. For example, g(0,0) - g(1,0) - g(2,0) - g(2,1) - g(2,2) - g(3,2) - g(4,2) - g(4,3) - g(4,4) - g(4,5) - g(4,6); this division will break the board such that coin O at c(3,2) is on one side, and coin X at c(1,4) and c(3,6) are on the other side.

Given the location of N coins on the board, determine the minimum number of swap needed among all possible divisions to achieve the goal (all coins on the same broken board have the same mark).


Input

The first line of input contains an integer T (1 ≤ T ≤ 100) the number of cases. Each case begins with three integers R, C, and N (1 ≤ R, C ≤ 1,000,000; 1 ≤ N ≤ 100) denoting the size of the board and the number of chips on the board respectively. The following N lines, each contains three integer ri, ci, and mi (1 ≤ ri ≤ R; 1 ≤ ci ≤ C; mi ∈ {O,X}) representing the location of ith coins – c(ri,ci) – and its mark respectively.

Output

For each case, output in a line the "Case #X: A" where X is the case number starts from 1., and A denotes the minimum number of swap needed among all possible divisions such that all coins on the same broken board have the same mark.


Sample InputOutput for Sample Input
4
4 6 3
1 4 X
3 2 O
3 6 X
2 2 4
1 1 X
1 2 O
2 1 O
2 2 X
3 3 9
1 1 X
1 2 O
1 3 X
2 1 O
2 2 X
2 3 O
3 1 X
3 2 O
3 3 X
100 100 1
20 15 X
Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 0