E — Chessboard Dancing

An amusement park anniversary organizing group invited a prominent dance company to perform surprise theme dances at the anniversary celebrations. The company prepared four dances with chess theme, conveniently named King performance, Knight performance, Bishop performance, and Rook performance.

Each dance is performed by a number of teams of dancers. The unusual setting in the amusement park seems to cause difficulties to some sensitive company members, however. The main choreographer holds that if a dancer, during a performance, has another dancer of the same team in his/her sight, it might sometimes confuse the dancer and tempt him/her to follow erroneously the movements of the teammate. The implication is that the dancers of the same team should be suitably dispersed over the dancing area to be mutually obscured by the members of other teams. Moreover, an arrangement of this kind cannot be shared among the performances, because their styles and movements differ dramatically from each other.

For each of the four dances, the organizing group eventually managed to formulate exact limiting conditions based on company demands:

The performance takes place on a regular S × S square grid of markers on the floor.

Each dancer occupies one marker, no marker is left unoccupied, no two dancers share a common marker, and each dancer remains at the same marker during the performance. Each dancer belongs to exactly one team.

Suppose that the center of each marker coincides with some integer lattice point in a Cartesian grid and that the distance between the center of any marker and the center of its closest neighbour marker is 1.

Let us consider two different markers A and B with their respective centers located at Cartesian coordinates (x₁, y₁) and (x₂, y₂).

• In the King performance, if |x₁ – x₂| < 2 and |y₁ – y₂| < 2, then A and B must be occupied by members of different teams.
• In the Knight performance, if |x₁ – x₂| · |y₁ – y₂| = 2, then A and B must be occupied by members of different teams.
• In the Bishop performance, if |x₁ – x₂| = |y₁ – y₂|, then A and B must be occupied by members of different teams.
• In the Rook performance, if |x₁ – x₂| · |y₁ – y₂| = 0, then A and B must be occupied by members of different teams.

For each of the four dances, the organizing group wants to know the minimum possible number of teams needed to perform the dance.

Input Specification

There are several test cases. Each test case consists of a single line with an integer S (1 ≤ S ≤ 1000) followed by a space and one of the four capital letters 'K', 'N', 'B', and 'R'. S specifies the size of the marker grid, and the letters denote King performance, Knight performance, Bishop performance, and Rook performance, respectively.

Output Specification

For each test case, print a single line with one integer denoting the minimum number of teams necessary to perform the given dance on a marker grid of the given size.

Sample Input

1. 2 N
2. 8 R
3. 2 B
4. 1 K

download as text file

Output for Sample Input

1. 1
2. 8
3. 2
4. 1

download as text file