There are two types of coordinate in a board of size R x C: gridcoordinate and cellcoordinate. 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. Gridcoordinate determines the position of each point (line intersection) on the board, starting from (0,0) at topleft most up to (R,C) at bottomright most of the board. On the other hand, cellcoordinate 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 topleft most up to (R,C) at bottomright most of the board. To differentiate these two coordinate system, we will refer gridcoordinate as g(row,col) and cellcoordinate as c(row,col). For example, g(2,1) corresponds to the point created by intersection of the 3^{rd} horizontal line from the top and the 2^{nd} vertical line from the left; c(2,3) corresponds to cell/area bounded by the 2^{nd} and 3^{rd} horizontal lines from the top and 3^{rd} and 4^{th} vertical lines from the left. See Figure 1 for clarity.
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.
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).
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 r_{i}, c_{i}, and m_{i} (1 ≤ r_{i} ≤ R; 1 ≤ c_{i} ≤ C; m_{i} ∈ {O,X}) representing the location of i^{th} coins – c(r_{i},c_{i}) – and its mark respectively.
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.
