Taco Partition Problem

In a mysterious forest, the creatures are arranged in a grid-like structure that is partitioned into clusters. Each cluster is composed of cells containing either a Dragon (D) or a Phoenix (P). You are given an odd number M of clusters and an odd number K of cells in each cluster (so that the total number of cells is N = M \times K). For each cluster, if the number of Dragons is strictly greater than the number of Phoenixes, the cluster is said to be won by the Dragon. The goal is to determine whether it is possible for the overall forest to have a Supreme creature of Dragon, that is, whether the number of clusters won by Dragons is strictly greater than \( \lfloor M/2 \rfloor \).

Note: Both M and K are odd integers. The victory condition for a test case is win if the number of winning clusters is greater than \( \lfloor M/2 \rfloor \); otherwise, it is a loss.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

1. The first line contains a single integer T, the number of test cases.
2. For each test case, there are two lines:
   1. The first line contains two space-separated integers M and K, where M is the number of clusters and K is the number of cells in each cluster.
   2. The second line contains a string of length M \times K consisting of characters 'D' (Dragon) and 'P' (Phoenix), representing the creatures in each cell.

outputFormat

For each test case, output a single line to standard output (stdout) with the integer 1 if it is possible for the forest to have the Supreme creature as a Dragon (i.e., the number of clusters where Dragons are in majority is greater than \( \lfloor M/2 \rfloor \)); otherwise, output 0.

## sample

8
3 3
DPDPDPDPD
5 1
DPDPD
3 5
DDPDDPPPDDPDPDP
3 3
DDDDDDDDD
3 3
PPPPPPPPP
3 3
DPDPDDPPD
3 5
DDPDDDDPDDPPDDD
3 3
DPDPDPPPP

1
1
0
1
0
1
1
0

</p>