체스판 위의 군무

놀이공원 창립 기념 행사를 준비하는 조직위원회가 이름난 무용단을 불러 기념 공연을 맡겼다. 무용단은 체스를 주제로 한 군무 네 편을 준비했고, 각각 킹 공연, 나이트 공연, 비숍 공연, 룩 공연이라고 부른다.

군무 한 편에는 여러 팀의 무용수가 함께 오른다. 수석 안무가는 공연 도중 무용수의 시야에 같은 팀 무용수가 들어오면 그 동작을 잘못 따라 하기 쉽다고 본다. 그래서 같은 팀 무용수는 다른 팀 무용수에게 가려지도록 무대 전체에 흩어 놓아야 한다. 네 공연은 동작과 분위기가 서로 많이 달라서 배치 하나를 여러 공연에서 함께 쓰지도 못한다.

조직위원회는 무용단의 요구를 공연마다 다음 조건으로 정리했다.

공연은 바닥에 놓인 $S \times S$ 정사각 격자 모양의 표식 위에서 진행한다. 무용수 한 명이 표식 하나를 차지하고, 비어 있는 표식은 없으며, 두 무용수가 표식 하나를 함께 쓰지 않는다. 각 무용수는 공연이 끝날 때까지 자기 표식에 머물고, 정확히 한 팀에 속한다.

표식의 중심은 모두 좌표평면의 격자점에 놓이고, 가장 가까운 두 표식의 중심 사이 거리는 1이다. 서로 다른 두 표식 A와 B의 중심 좌표를 각각 $(x_1, y_1)$, $(x_2, y_2)$라고 하자.

• 킹 공연에서는 $|x_1 - x_2| < 2$이고 $|y_1 - y_2| < 2$이면 A와 B에 선 두 무용수가 서로 다른 팀이어야 한다.
• 나이트 공연에서는 $|x_1 - x_2| \times |y_1 - y_2| = 2$이면 A와 B에 선 두 무용수가 서로 다른 팀이어야 한다.
• 비숍 공연에서는 $|x_1 - x_2| = |y_1 - y_2|$이면 A와 B에 선 두 무용수가 서로 다른 팀이어야 한다.
• 룩 공연에서는 $|x_1 - x_2| \times |y_1 - y_2| = 0$이면 A와 B에 선 두 무용수가 서로 다른 팀이어야 한다.

네 공연 각각에 대해 공연을 올리는 데 필요한 팀 수의 최솟값을 구하라.

입력은 여러 개의 테스트 케이스로 이루어지고 파일의 끝까지 이어진다. 각 줄에는 정수 $S$ ($1 \le S \le 1000$)와 공백 하나, 그리고 대문자 K, N, B, R 중 하나가 주어진다. $S$는 표식 격자의 크기이고, 네 글자는 각각 킹 공연, 나이트 공연, 비숍 공연, 룩 공연을 뜻한다.

각 테스트 케이스마다 주어진 크기의 표식 격자에서 해당 공연을 올리는 데 필요한 팀 수의 최솟값을 한 줄에 하나씩 출력한다.