패션쇼

새 옷 세 가지를 선보이는 패션쇼를 연다. 무대는 $N \times N$ 격자다.

각 칸은 비어 있거나 모델 한 명이 서 있다. 모델이 입은 옷은 +, x, 가장 인기가 많은 o 중 하나다. + 모델이나 x 모델이 있는 칸은 쇼에 스타일 점수 1점을 더하고, o 모델이 있는 칸은 2점을 더한다. .으로 적는 빈 칸은 점수를 더하지 않는다.

모델이 설 수 있는 자리에는 규칙 두 가지가 있다.

• 두 모델이 같은 행이나 같은 열에 있으면 둘 중 적어도 하나는 +다.
• 두 모델이 같은 대각선에 있으면 둘 중 적어도 하나는 x다.

$i_0$행 $j_0$열의 모델과 $i_1$행 $j_1$열의 모델은 $i_0 = i_1$이면 같은 행에 있고, $j_0 = j_1$이면 같은 열에 있으며, $i_0 + j_0 = i_1 + j_1$이거나 $i_0 - j_0 = i_1 - j_1$이면 같은 대각선에 있다.

다음 배치는 규칙 두 가지를 모두 어긴다.

...
x+o
.+.

가운데 행에 있는 두 모델 x와 o 중에는 +가 없다. 맨 아래 행의 +에서 가운데 행의 o로 이어지는 대각선에는 모델이 둘 있는데 어느 쪽도 x가 아니다.

다음 배치는 어느 행, 열, 대각선도 규칙을 어기지 않으므로 올바르다.

+.x
+x+
o..

스타일리스트가 규칙을 지켜 모델 $M$명을 이미 배치해 두었다. 빈 칸에는 원하는 옷을 입은 모델을 몇 명이든 추가로 세울 수 있고, 한 명도 세우지 않아도 된다. 이미 서 있는 모델을 뺄 수는 없지만, 마지막 배치가 규칙 두 가지를 지키는 한 + 모델과 x 모델을 원하는 만큼 o 모델로 바꿔 입힐 수 있다.

예를 들어 $3 \times 3$ 무대가 다음처럼 시작한다고 하자.

...
+++
x..

1행 2열에 x를 세우고 2행 3열의 +를 o로 바꾸면 스타일 점수가 6점이 되고, 이 무대에서 이보다 높은 점수를 내는 배치는 없다.

.x.
++o
x..

얻을 수 있는 스타일 점수의 최댓값을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$과 $M$이 주어진다. 이어서 $M$개의 줄이 주어지며, 그중 $i$번째 줄에는 모델이 입은 옷을 나타내는 문자 하나(+, x, o 중 하나)와 그 모델의 위치를 나타내는 정수 $R_i$, $C_i$가 주어진다. 행 번호는 위에서 아래로 1번부터 $N$번까지이고, 열 번호는 왼쪽에서 오른쪽으로 1번부터 $N$번까지다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 얻을 수 있는 스타일 점수의 최댓값이다.

• $1 \le T \le 100$
• $1 \le N \le 100$
• $0 \le M \le N^2$
• 모든 $i$에 대해 $1 \le R_i \le N$
• 모든 $i$에 대해 $1 \le C_i \le N$
• 미리 배치된 모델 중 같은 칸에 있는 둘은 없다.
• 미리 배치된 모델은 규칙 두 가지를 지킨다.