We are given a rectangular board, and on the board we need to place rooks. Recall, that a rook attacks all fields that are in the same horizontal and the same vertical line. We want to place as many rooks that do not attack themselves as possible. The task would be trivial if not for two complications. First, there might be pawns on the board. If a pawn is in the same line as a rook, then the rook attacks all fields between itself and the pawn, but no fields behind the the pawn. Obviously, we cannot place a rook on a field with a pawn. Second, there might be reserved fields on which we just cannot place a rook.

Input

The first line of the input contains an integer t <=5, the number of test cases. t test cases follow.

The first line of each test case consists of two integers X <= 300 and Y <= 300, separated by a single space. Next, X lines follow, each having Y letters separated by spaces. The jth letter on the i-th line is one of the following (quotes are for clarity, and do not appear in the input):

1. "A", if the field (i, j) is available for putting a rook there.
2. "P", if the field (i, j) contains a pawn.
3. "R", if the field (i, j) is reserved.

Output

A single line for each test case containing an integer denoting the maximum number of rooks that do not attack themselves.

Example

Input:
5
4 7
A A A A A A A
A A A A A A A
A A A A A A A
A A A A A A A
4 7
A A A A A A A
A A A A A A A
A A A A A A A
R R R R R R R
4 7
A A A P A A A
A A A P A A A
A A A P A A A
R R R R R R R
3 3
R A R
A R A
R A R
3 3
P A P
A P A
P A P

Output:
4
3
6
2
4