Hover is playing a computer game called "Finding treasures", where the target is to collect as many treasures as possible.
The game is played on a rectangle map divided into m rows and n columns. Some grids are safe; some grids are dangerous, while some have hidden treasures. Hover's robot set out from the northwest corner. It move east, west, south, and north to adjacent grids, denoted as 'E', 'W', 'S', and 'N' respectively. The east and the west boundary are considered connected, so are the north and the south boundary. So when the robot goes out from one side, it will appear from the opposite side. The robot has a prestored moving sequence which is set by Hover. The robot will move according to the prestored moving sequence. When it comes to the end of the sequence, it will turn to the beginning again, round and round.
The robot can detect adjacent grid's state (safe or dangerous), but can only find treasures in the current grid. When it finds that its current moving direction will go into dangerous grid, it will skip it, continuing to the next direction in the sequence. When it goes into a grid with treasure it will collect it.
Given the map of the island, the moving sequence Hover sets, you are to find out the number of treasures the robot can collect.
The first line is the number of test cases.
For each test case, the first line is two integers - m and n (1<=m, n<=50).
Then m lines follow, describing the map. Safe grids are marked with '.', dangerous grids are marked with '#', while grids with treasure are marked with 'T'.
The last line is the robot's prestored sequence, no longer than 50 characters.
For each test case, output one line containing the number of treasures the robot can collect.