High School Programming League Problems Archive

Most likely everyone knows the game of chess. See the rules and movements of chess figures if you are an exception.

In this problem chess pieces will be denoted as follows:

P - pawn

T - rook

S - knight

L - bishop

K - king

D - queen.

Black pieces will be denoted with lowercase letters and white ones with uppercase letters.

In the current situation, white is to move and its pawns moves upward on the board.

Your task is to calculate the number of different moves allowed for white.

Exceptions:

• Since we do not know the history of the given position, do not count castling as an allowed move
• Also do not count en passant as an allowed move (even if it seems that situation on the board allows this special type of move).
• If there is a possibility for Pawn promotion calculate this as four different moves because chess pieces of four different types (rook, knight, bishop, queen) are allowed in place of the promoted pawn.
• It is possible that the white king is checked in the given position.
• It is guaranteed that the white king has not been checkmated in the given position.
• Stalemate is allowed in the given position.

Input

The first line contains an integer T, the number of tests. (T<=10).

In the next 9xT lines you are given T tests. Each test represents some state of a chess game (for us this is the current position). Pieces are denoted by letters: K, D, L, S, T, P or k, d, l, s, t, p. Empty fields are represented with dots ('.'). Tests will be separated by an empty line (as will be the first test from T).

Output

For every test, in a new line, print a single integer, representing the number of different moves allowed for white.

Input:
2

tsldklst
pppppppp
........
........
........
........
PPPPPPPP
TSLDKLST

........
........
........
....k...
d.......
...K....
........
........

Output:
20
4

Input data

set  description
 1   Only kings and pawns can be on the board. No pawn promotion. No checked white king. No stalemate.
 2   Kings, pawns, knights can be on the board. No pawn promotion.
 3   Any kind of piece except queens can be on the board.
 4   Any kind of piece can be on the board.
 5   Any kind of piece can be on the board.

Scoring

By solving this problem you score 10 points (2 points for every correctly solved test set).