Fashion Show

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

Each cell is either empty or holds exactly one model. A model wears one of three styles, written +, x, and the top style o. A cell with a + model or an x model adds 1 style point to the show. A cell with an o model adds 2 style points. An empty cell, written ., adds nothing.

Two rules control where models may stand.

• 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$, column $j_0$ and a model in row $i_1$, 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$.

This arrangement breaks both rules:

...
x+o
.+.

The middle row holds two models (x and o) and neither 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 is an x.

This arrangement is legal, because 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 you like on empty cells, including none. You may not remove a model, but you may upgrade as many + models and x models into o models as you wish, as long as the final arrangement still follows both rules.

For example, a 3 by 3 stage may start like this:

...
+++
x..

Adding an x in row 1, column 2 and upgrading the + in row 2, column 3 into an o gives 6 style points, and no arrangement on this stage gives more:

.x.
++o
x..

Report the largest number of style points you can reach.

The first line holds the number of test cases $T$. Each test case begins with one line holding two integers $N$ and $M$. Then $M$ lines follow. The $i$-th of these lines 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 that model. Rows are numbered 1 through $N$ from top to bottom, and columns are numbered 1 through $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 number of style points you can reach.

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