한 수에 잡히는 경우의 수

기물이 놓인 체스판이 주어진다. 한 수 만에 기물이 잡히는 서로 다른 경우의 수를 모두 세어라. 이 문제에서는 기물의 색을 구분하지 않는다. 즉 규칙에만 맞으면 어떤 기물이든 다른 기물을 잡는다.

칸은 알파벳 한 글자와 숫자 한 자리로 A1, A2, ..., A8, B1, ..., H8과 같이 나타낸다. 알파벳은 A부터 H까지, 숫자는 1부터 8까지다.

기물의 종류와 움직임은 다음과 같다.

• (K) 킹은 여덟 방향으로 한 칸 움직인다.
• (Q) 퀸은 여덟 방향으로 원하는 칸 수만큼 움직이지만, 다른 기물을 뛰어넘지 못한다.
• (R) 룩은 가로 또는 세로로만 움직이며, 다른 기물을 뛰어넘지 못한다.
• (B) 비숍은 대각선으로만 움직이며, 다른 기물을 뛰어넘지 못한다.
• (N) 나이트는 한 방향으로 두 칸, 거기서 직각 방향으로 한 칸 떨어진 칸으로 움직이고, 사이에 있는 기물을 뛰어넘는다.
• (P) 폰은 알파벳이 커지는 쪽(A에서 B, B에서 C)의 대각선으로 움직일 때만 잡는다. 알파벳이 $c$이고 숫자가 $r$인 칸에 있는 폰은 알파벳이 $c$의 다음 글자이면서 숫자가 $r-1$ 또는 $r+1$인 두 칸만 공격한다.

퀸, 룩, 비숍은 한 방향으로 나아가다가 기물이 있는 칸에서 멈춘다. 따라서 각 방향에서 가장 가까운 기물만 잡는다.

경우의 수는 (잡는 기물, 잡히는 기물) 순서쌍의 개수로 센다. B2에 킹, A1에 폰, H8에 퀸이 있으면 답은 3이다. H8 퀸이 B2 킹을 잡고, A1 폰이 B2 킹을 잡고, B2 킹이 A1 폰을 잡는다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 기물의 개수 $N$이 주어지고, 이어서 $N$개의 줄에 기물이 하나씩 위치-종류 형식으로 주어진다. 예를 들어 A1-K는 A1에 킹이 있다는 뜻이다. 종류는 K, Q, R, B, N, P 중 하나이고, 같은 칸에 두 기물이 놓이는 경우는 없다. 테스트 케이스 사이에는 빈 줄이 들어가기도 한다.

제한

• $1 \le T \le 100$
• $1 \le N \le 64$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 한 수 만에 기물이 잡히는 서로 다른 경우의 수이다.