H. Gas Stations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stations.in
output
standard output

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?

Input

The 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.

Output

For each test case, print the answer on a single line.

Example
Input
5
1
+
3
+..
4
+.+.
5
.+...
10
..+.....++
Output
0
1
1
2
2