Its 2000BC, there is a war is going on between the Greece and Rome, the army of Rome is headed by himself their god of war, Mars, on the the side of the Greece there is their faithful and ever-winning general Kratos, who has got the power from lordPoseidon by defeating the extremely powerful Hydra, the power to blow is his enemies into ashes by firing the lightning bolt from his hand, called Poseidon's Rage.

This power is the only hope of Kratos, only by this power he can destroy Mars, but the Poseidon's Rage has a limitation, it can only travel in straight line and the goes in only horizontal and vertical direction, and only can be deflected by iron-cored Topaz, and only they reflect the lightning bolt in 90 degree angle, in 2 sides, like if bolt is going in direction of east then iron-cored Topaz can deflect them in 2 directions in North or in South, and similarly for the other directions, as iron-cored Topaz are found in two states for used for reflecting in 2 directions.

Now the war was going on, Kratos knows the position of Mars, and the battlefield can be thought to be the 2-D matrix of of cells, where '.' in the field represents the empty place, '*' represents the position of a wall, Poseidon's Rage can not pass wall, 'K' represents the position of kratos and 'M' represents the position of Mars, now if Kratos wants to kill Mars, then he has to fire the Poseidon's Rage as it can be deflected by using the iron-cored Topaz, he needs to put some(possibly 0) iron-cored Topaz plates in the field, luckly he can easily put them in the field where he finds the empty place by using his magic in no time, but the iron-cored Topaz are very rare items and can be bought at very high rates, so he needs to minimize the amount of iron-cored Topaz so that he could also kill Mars, now Kratos is very weak in logic, he only used his time to built his muscles, so he asks you for his assistance, help Kratos to kill Mars.

Input:

The first time will have a single integer 't' the number of the test cases in the problem, for each test case, first line will contain m and n the number of cells in one row and in one column, then there will be there will be n lines, each line containing m characters, which can be '.' empty field, '*' the wall, 'K' the Kratos and 'M' the Mars.

Output:

Output the minimum number of the iron-cored Topaz( any state of iron-cored Topaz used) required to kill Mars by using his Poseidon's Rage for each testcase.

Constraints:

1 <= m, n <= 1000 1 <= t <= 5