Tourist Walk
The Olympics is a sporting event of global significance. The city chosen to host the Olympic Games always aims to impress the millions of fans who come to support their teams, as well as the athletes and everyone for whom the Games transcend national and continental boundaries.
London has a rich history of hosting the Olympics: the capital of Great Britain hosted the Games for a record third time in 2012. On the previous two occasions, in 1908 and 1948, circumstances prevented the organization of a grand celebration, so this time it was decided to celebrate on a grand scale.
However, the English approached the construction of Olympic facilities with typical British pragmatism, employing a strategy of economical building. Modern materials were used in the construction of the arenas, allowing for their quick and easy dismantling after the competitions.
Special maps highlighting Olympic (and other) notable places in London were created for the numerous visitors. One of these maps ended up in Vasya's hands. With a little free time from the competitions he was interested in, he wants to take a sightseeing tour, visiting as many interesting sites marked on the map as possible.
The street traffic rules in London are quite unique, but Vasya decided not to learn them thoroughly—he discovered that if he travels from his hotel, located in the northwestern part of the city, only south or east, and returns only west or north, he never encounters any issues.
Your task is to design such a route for Vasya so that he, following his rules, visits as many notable places in Olympic London as possible and returns to the hotel.
Input
The first line of the input file specifies the number of test cases (no more than 20). Each test case begins with a line containing two numbers: W and H (2 ≤ W, H ≤ 100), representing the width and height of the map. The next H lines of each test case contain W characters each and denote:
'.' - a free area that can be moved through;
'*' - an interesting object (also an area accessible for movement);
'#' - blocked areas (not accessible for movement).
You can assume that there is always a path from the hotel where Vasya is staying, located in the top left corner of the map, to the bottom right corner of the map.
Output
For each test case, output a single number on a separate line—the maximum number of interesting objects Vasya can visit. The same interesting Olympic or tourist object visited twice is counted only once.