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.

Single Round Match #09
3 hour contest



Announcement

Problem Tags
adhoc

Supported by our Coding Partner