패션쇼

새로 만든 세 가지 스타일의 옷을 선보이는 패션쇼를 연다. 무대는 $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 모델로 바꿀 수 있다.

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

첫째 줄에 테스트 케이스의 수 $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$, $1 \le C_i \le N$
• 미리 세워 둔 두 모델이 같은 칸에 서는 경우는 없다.
• 미리 세워 둔 모델은 두 규칙을 모두 지킨다.

첫 번째 예제에는 테스트 케이스가 세 개 있다.

첫 번째 테스트 케이스의 무대는 $2 \times 2$이고 처음에는 비어 있다. 아래 배치가 4점을 얻는다.

x.
+o

두 번째 테스트 케이스는 하나뿐인 칸에 이미 o 모델이 서 있어서 더 세우거나 바꿀 수 없고, 점수는 2점이다.

세 번째 테스트 케이스의 처음 무대는 다음과 같다.

...
+++
x..

아래 배치가 6점을 얻는다.

.x.
++o
x..