Fashion Show

You are hosting a fashion show for three new styles of clothing. The stage is an $N \times N$ grid of cells.

Each cell is either empty, written as ., or holds one model. A model wears one of three styles: +, x, or o. A cell with a + model or an x model adds 1 style point. A cell with an o model adds 2 style points. An empty cell adds nothing.

Two rules govern how the models stand relative to each other.

• Whenever two models share a row or a column, at least one of the two is a +.
• Whenever two models share a diagonal, at least one of the two is an x.

A model in row $i_0$ and column $j_0$ and a model in row $i_1$ and column $j_1$ share a row if $i_0 = i_1$, share a column if $j_0 = j_1$, and share a diagonal if $i_0 + j_0 = i_1 + j_1$ or $i_0 - j_0 = i_1 - j_1$.

The grid below breaks both rules.

...
x+o
.+.

The middle row holds the pair x and o, and neither of them is a +. The diagonal that runs from the + in the bottom row up to the o in the middle row holds two models, and neither of them is an x.

The grid below is legal. No row, column, or diagonal breaks a rule.

+.x
+x+
o..

Your advisor has already placed $M$ models, and that placement follows both rules. You may add any number of models of any styles, including none at all. You may not remove a model, but you may upgrade as many of the existing + and x models into o models as you wish, as long as the rules still hold.

Print the largest total number of style points you can reach.

The first line has the number of test cases $T$. Each test case begins with a line holding two integers $N$ and $M$. Then $M$ lines follow, and the $i$-th of them holds one character (+, x, or o, the style of the model) and two integers $R_i$ and $C_i$, the row and the column of the model. Rows are numbered 1 to $N$ from top to bottom, and columns are numbered 1 to $N$ from left to right.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the largest total number of style points.

• $1 \le T \le 100$
• $1 \le N \le 100$
• $0 \le M \le N^2$
• $1 \le R_i \le N$ and $1 \le C_i \le N$ for every $i$
• No two pre-placed models sit in the same cell.
• The pre-placed models follow both rules.

The first example holds three test cases.

In test case 1 the stage is 2 by 2 and starts empty. The arrangement below earns 4 points.

x.
+o

In test case 2 the only cell already holds an o model, so nothing can be added or changed, and the score is 2.

In test case 3 the stage starts like this.

...
+++
x..

The arrangement below earns 6 points.

.x.
++o
x..