404684: GYM101608 H Gas Stations
Description
The city of single direction consists of n blocks in a row, numbered from 1 to n from left to right. All of them are populated by citizens, and some of them has gas stations. People in each block will go to the nearest block that has a gas station. The distance between two blocks i and j is |i - j|, where |x| is the absolute value of x.
The government wants to move at most one station from its original block to another block. What is the maximum distance that a citizen has to cross to get to his/her nearest station, if the government operated in a way that minimizes this distance?
InputThe first line of input contains a single integer T (1 ≤ T ≤ 1200), the number of test cases.
The first line of each test case contains a single integer n (1 ≤ n ≤ 105), the number of blocks in the city.
The second line contains a string s of n characters, each character is either ‘+’, which represents a block with one gas station, or ‘.’ which represents a normal block.
It is guaranteed that there’s at least one block that has a gas station.
The total sum of n overall test cases doesn't exceed 5 × 106.
OutputFor each test case, print the answer on a single line.
ExampleInput5Output
1
+
3
+..
4
+.+.
5
.+...
10
..+.....++
0
1
1
2
2