Go Back

##### Grenade Matrix (100)

Description

A team of players is stuck in a building, and grenades are being thrown into the building. Hence, a matrix of size MxN is formed, with players, grenades and empty spots where the grenades are denoted by “G”, the players are denoted by “P”, and empty spots denoted by “*”. The player will die if there is a grenade in any of the 8 blocks surrounding the player. Count the number of players that survive the grenade attacks.

Input

The first line contains X number of test cases.

The second line contains M and N, number of columns and rows respectively.

The next N lines contains M non-spaced characters to form the matrix.

Output

X lines contains number of players that survive.

Constraints

1 <= X <= 1000

1 <= M < N <= 1000

Example

Copy Input

Input:

1

10 11

Output:

4

Explanation

There are a total of 8 players, out of which 4 have grenades in adjacent blocks. Hence 4 players survive the blast.