Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3262
Game of Pawns

Time Limit: 5 Seconds      Memory Limit: 32768 KB

On the chess board, the poor little pawns are put out in front right in harms way while the other guys are hiding back behind.But according the chess rules, if a pawn can make it to the other side, it will be rewarded with a promotion - to a queen! Noting this, EZ invents a new kind of single-player game.

At the beginning of the game, EZ puts 8 black pawns on the first rank(see the figure below), and then places some enemy on the board. He wonder how many of them can become queens at most.

Here are some rules in this game about the move of the pawn. You can see more detail in Rules of Chess

  • A pawn can move forward one square, if that square is unoccupied. If it has not yet moved, the pawn has the option of moving two squares forward provided both squares in front of the pawn are unoccupied. A pawn cannot move backward.
  • Pawns are the only pieces that capture differently from how they move. They can capture an enemy piece on either of the two spaces adjacent to the space in front of them (i.e., the two squares diagonally in front of them) but cannot move to these spaces if they are vacant.
  • If a pawn advances to its eighth rank,it is then promoted to a queen. In this very game, once a pawn has been promoted to a queen, it would stay there for the rest of the game.
Since this is a single-player game, the enemy would stay where they are during the whole game(unless they had been captured).


There are multiple cases (no more than 30). The first line of each test case contains an integer N, indicating the number of enemys on the board. (0 <= N <= 16) Then N lines followed, each line contains two character cr ('a' <= c <= 'h', '1' < r <= '8'), which is the loction of the ith enemy.


For each case, output the maximum number of pawns that can be promoted to queens in a single line.

Sample Input


Sample Output


Author: WANG, Yelei
Source: ZOJ Monthly, November 2009
Submit    Status