A. Iskander and Drawings

题目描述

During a geometry lesson, Iskander got very bored, so he decided to draw in Yura’s notebook. To do this, he took a row and drew horizontal lines on it. Some lines are long, some are short, and some parts of the page remain empty.

TheThe page is represented by a string s , where the character ‘*’ denotes an empty part of the paper, and the character ‘#’ denotes one centimeter of a drawn line. A continuous sequence of ‘#’ characters forms a single line.

Yura decided to erase all the lines and made Iskander help him: they will erase one of the lines from both ends simultaneously.

Each second, Iskander erases 1 centimeter from the right end of the line, and Yura erases 1 centimeter from the left end.

If the current length of the line is 1 or 2 centimeters, then in the next second it is erased completely, and the process ends.

Yura wants to choose a line so that, together with Iskander, they erase it for as long as possible. Help him determine this maximum time. If there are no lines on the page, the answer is 0 seconds.

输入输出

Input

The first line contains a single integer t(1≤t≤2500) — the number of test cases.

The first line of each test case contains an integer n(1≤n≤10) — the length of the string s.

The second line of each test case contains a string sof length n, consisting of characters ‘#’ and ‘*’.

Output

For each test case, output a single integer — the maximum time required to erase a line.

Example

Input

5
7
#*##*##
8
########
8
********
8
#*****##
6
*#####

Output

1
4
0
1
3

解题思路

原本以为是模拟，但是后面发现，本题实际上是贪心，两人从两边分开擦除，每次擦除1个单位，所以最大时间就是每段线的长度的一半，因为1-2时，直接擦除即可。所以总时间是每段线的长度的一半向上取整。

代码如下：

// Problem: A. Iskander and Drawings
// Contest: Codeforces - Codeforces Round 1109 (Div. 3)
// URL: https://codeforces.com/contest/2244/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	while(n--){
		int m;
		cin>>m;
		string s;
		cin>>s;
		int res=0,t=0;
		for(auto i:s){
			if(i=='#')t++;
			else t=0;
			res=max(res,(t+1)/2);
		}
		cout<<res<<'\n';
	}
	return 0;
}