Chessboard Dancing

Problem

The committee preparing the anniversary of an amusement park invited a well known dance company to put on the celebration performances. The company prepared four group dances on a chess theme, called the king performance, the knight performance, the bishop performance and the rook performance.

Several teams of dancers appear in each dance. The chief choreographer holds that a dancer who sees a teammate during a performance is likely to copy that teammate's movements by mistake. Dancers of the same team therefore have to be spread over the stage so that dancers of other teams hide them. The four performances differ so much in movement and mood that one arrangement cannot be reused across them.

The committee turned the company's demands into the following conditions, one set per performance.

A performance takes place on a square $S \times S$ grid of markers on the floor. One dancer occupies one marker, no marker is left empty, and no two dancers share a marker. Each dancer stays on the same marker for the whole performance and belongs to exactly one team.

The center of every marker lies on an integer lattice point of a Cartesian grid, and the distance between the centers of two closest markers is 1. Take two different markers A and B whose centers are at $(x_1, y_1)$ and $(x_2, y_2)$ .

In the king performance, if $|x_1 - x_2| < 2$ and $|y_1 - y_2| < 2$ , then the dancers on A and B must belong to different teams.
In the knight performance, if $|x_1 - x_2| \times |y_1 - y_2| = 2$ , then the dancers on A and B must belong to different teams.
In the bishop performance, if $|x_1 - x_2| = |y_1 - y_2|$ , then the dancers on A and B must belong to different teams.
In the rook performance, if $|x_1 - x_2| \times |y_1 - y_2| = 0$ , then the dancers on A and B must belong to different teams.

For each of the four dances, find the minimum number of teams needed to perform it.

Input

The input holds several test cases and continues until the end of the file. Each line contains an integer $S$ ( $1 \le S \le 1000$ ), one space, and one of the capital letters K, N, B, R. $S$ is the size of the marker grid, and the four letters denote the king performance, the knight performance, the bishop performance and the rook performance.

Output

For each test case, print on its own line the minimum number of teams needed to perform the given dance on a marker grid of the given size.