Description
My Kingdom is a facebook game which is developed by Happy Elements. In this game, you help the king to develop the kingdom. You can grow crops, train the army, build shops and get money and etc. There are also some mini games, such as BrickBreaker. You can get money or items in the mini game.This time a new update version is coming. They add a mini game called "Mystery Shape". The shape pattern is like the picture below.
You need to put as much as you can on a given plate to earn more award. The pattern can be rotated and flipped. For example, given the 5 x 5 plate below and the place with X is the forbidden area. In this case you can put at most 3 pieces of this pattern.
Input
The first line of the input is an integer Z (1 ≤ Z ≤ 30), which means the number of test cases below. The first line of a test case contains two integers N and M, where N is the height of the plate and M is the width of the plate (3 ≤ N ≤ 7, 3 ≤ M ≤ 7). The following N lines describe the plate. Each line contains M characters. The character '.' means it is an empty area, you can put the shape on it. And the character 'X' means it is an forbidden area, you can't put the pattern on it.
Output
For each test case, print an integer on a line which means the maximum number of pieces of the pattern you can put on the plate.