Itz Chess

기물이 배치된 체스판이 주어질 때, 임의의 기물이 한 번의 수로 잡힐 수 있는 서로 다른 방법의 총수를 구한다. 참고: 이 문제에서는 색과 관계없이 기물을 잡을 수 있다.

예를 들어, 기물이 3개 있고 King이 B2, Pawn이 A1, Queen이 H8에 있다면 잡힐 수 있는 기물의 총수는 3이다. H8-Q은 B2-K을 잡을 수 있고, A1-P은 B2-K을 잡을 수 있으며, B2-K은 A1-P을 잡을 수 있다.

체스판의 위치는 A1, A2... A8,B1.. H8로 표현한다.

기물은 다음과 같이 표현한다.

• (K) King은 8 방향으로 한 칸 이동할 수 있다.

• (Q) Queen은 8 방향으로 원하는 만큼 이동할 수 있지만, 다른 기물을 뛰어넘을 수 없다.

• (R) Rook은 수직 또는 수평으로만 이동할 수 있지만, 다른 기물을 뛰어넘을 수 없다.

• (B) Bishop은 대각선으로만 이동할 수 있지만, 다른 기물을 뛰어넘을 수 없다.

• (N) Knight는 수평으로 두 칸과 수직으로 한 칸 떨어진 칸 OR 수평으로 한 칸과 수직으로 두 칸 떨어진 칸으로 이동할 수 있다.

• (P) Pawn은 대각선 위쪽(더 큰 번호를 향하는 방향, 즉 A -> B, B->C 등의 방향)으로 이동해야만 기물을 잡을 수 있다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10. 기물에는 K, P가 포함될 수 있다.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 64.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 기물의 수 N으로 구성된다. 이어지는 N개의 줄에는 각각 기물이 있는 위치와 - 기호, 기물의 종류가 차례로 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 임의의 기물이 잡힐 수 있는 서로 다른 방법의 총수이다.