#include<bits/stdc++.h>
using namespace std;
 
#define ff              first
#define ss              second
#define pb              push_back
#define int             long long
#define mp              make_pair
#define pr              pair<long long,long long>
#define vr              vector<long long>
#define MOD          1000000007
#define mod         1000000007
#define mod2            998244353
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define ll              long long
#define ld	            long double
#define w(x)            int x; cin>>x; while(x--)
#define fill(a,b)       memset(a, b, sizeof(a))
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 200010;
 int spf[N];
 void sieve()
 {
     for(int i=1;i<=N;i++)
      spf[i]=i;
      
    for(int i=2;i<=N;i=i+2)
     spf[i]=2;
     
    for(int i=3;i*i<=N;i=i+2)
    {
        if(spf[i]==i)
        {
            spf[i]=i;
            for(int j=i*i;j<=N;j=j+i)
            {
                if(spf[j]==j)
                {
                    spf[j]=i;
                }
            }
        }
    }
 }
 int power(int x, unsigned int y) 
{ 
    int res = 1;     // Initialize result 
   
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = res*x%mod; 
   
        // y must be even now 
        y = y>>1; // y = y/2 
        x = x*x % mod;  // Change x to x^2 
    } 
    return res%mod; 
}
int modInv(int a){return power(a,MOD-2);}
int fact[N],inv[N];
void factorial(int n){
	fact[0]=1;
	for(int i=1;i<=n;i++){
		fact[i]=fact[i-1]*i;
		if(fact[i]>=MOD)
			fact[i]%=MOD;
	}
}
void InvFactorial(int n){
	inv[0]=1;
	for(int i=1;i<=n;i++)
		inv[i]=modInv(fact[i]);
}
int ncr(int n,int r){
	if(n<r||n<0||r<0)
		return 0;
	int b=inv[n-r];
	int c=inv[r];
	int a=fact[n]*b;
	if(a>=MOD)
		a%=MOD;
	a*=c;
	if(a>=MOD)
		a%=MOD;
	return a;
}
bool isPrime(int n) 
{ 
    // Corner case 
    if (n <= 1) 
        return false; 
  
    // Check from 2 to n-1 
    for (int i = 2; i*i<= n; i++) 
        if (n % i == 0) 
            return false; 
  
    return true; 
}
int countDigit(long long n)
{
    int count = 0;
    while (n != 0)
    {
        n = n / 10;
        ++count;
    }
    return count;
}
void solve() {
 
  int n;
  cin>>n;
  
  string s;
  cin>>s;
  
  int pre[n];
  int c=0;
  pre[0]=0;
  if(s[0]=='*')c++;
  for(int i=1;i<n;i++){
      if(s[i]=='*')
      {
          pre[i]=pre[i-1];
          c++;
          
      }
      else{
          pre[i]=pre[i-1]+c;
      }
  }
  
  int suf[n];
  suf[n-1]=0;
  
  c=0;
  if(s[n-1]=='*')c++;
  for(int i=n-2;i>=0;i--){
       if(s[i]=='*')
      {
          suf[i]=suf[i+1];
          c++;
          
      }
      else{
          suf[i]=suf[i+1]+c;
      }
  }
  int ans=min(suf[0],pre[n-1]);
  
  /*for(int i=0;i<n;i++)cout<<suf[i]<<" ";
  cout<<"\n";*/
  for(int i=0;i<n-1;i++){
     ans=min(ans,pre[i]+suf[i+1]);
  }
  
  
  cout<<ans<<"\n";
}

int32_t main()
{ 
      ios;
      int test;
      
     
      test=1;
      int cas=1;
     factorial(N-1);
      InvFactorial(N-1);
     // sieve();
    
     
      cin>>test;
      while(test--)
      {
         //cout<<"Case #"<<cas<<": ";
         solve();
         cas++;
       
        }
   
 
 
       
    
    return 0;
}
### Prompt

Your task is to create a CPP solution to the following problem:

You are playing the game "Arranging The Sheep". The goal of this game is to make the sheep line up. The level in the game is described by a string of length n, consisting of the characters '.' (empty space) and '*' (sheep). In one move, you can move any sheep one square to the left or one square to the right, if the corresponding square exists and is empty. The game ends as soon as the sheep are lined up, that is, there should be no empty cells between any sheep.

For example, if n=6 and the level is described by the string "**.*..", then the following game scenario is possible: 

  * the sheep at the 4 position moves to the right, the state of the level: "**..*."; 
  * the sheep at the 2 position moves to the right, the state of the level: "*.*.*."; 
  * the sheep at the 1 position moves to the right, the state of the level: ".**.*."; 
  * the sheep at the 3 position moves to the right, the state of the level: ".*.**."; 
  * the sheep at the 2 position moves to the right, the state of the level: "..***."; 
  * the sheep are lined up and the game ends. 



For a given level, determine the minimum number of moves you need to make to complete the level.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 10^6).

The second line of each test case contains a string of length n, consisting of the characters '.' (empty space) and '*' (sheep) — the description of the level.

It is guaranteed that the sum of n over all test cases does not exceed 10^6.

Output

For each test case output the minimum number of moves you need to make to complete the level.

Example

Input


5
6
**.*..
5
*****
3
.*.
3
...
10
*.*...*.**


Output


1
0
0
0
9

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
 
#define ff              first
#define ss              second
#define pb              push_back
#define int             long long
#define mp              make_pair
#define pr              pair<long long,long long>
#define vr              vector<long long>
#define MOD          1000000007
#define mod         1000000007
#define mod2            998244353
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define ll              long long
#define ld	            long double
#define w(x)            int x; cin>>x; while(x--)
#define fill(a,b)       memset(a, b, sizeof(a))
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 200010;
 int spf[N];
 void sieve()
 {
     for(int i=1;i<=N;i++)
      spf[i]=i;
      
    for(int i=2;i<=N;i=i+2)
     spf[i]=2;
     
    for(int i=3;i*i<=N;i=i+2)
    {
        if(spf[i]==i)
        {
            spf[i]=i;
            for(int j=i*i;j<=N;j=j+i)
            {
                if(spf[j]==j)
                {
                    spf[j]=i;
                }
            }
        }
    }
 }
 int power(int x, unsigned int y) 
{ 
    int res = 1;     // Initialize result 
   
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = res*x%mod; 
   
        // y must be even now 
        y = y>>1; // y = y/2 
        x = x*x % mod;  // Change x to x^2 
    } 
    return res%mod; 
}
int modInv(int a){return power(a,MOD-2);}
int fact[N],inv[N];
void factorial(int n){
	fact[0]=1;
	for(int i=1;i<=n;i++){
		fact[i]=fact[i-1]*i;
		if(fact[i]>=MOD)
			fact[i]%=MOD;
	}
}
void InvFactorial(int n){
	inv[0]=1;
	for(int i=1;i<=n;i++)
		inv[i]=modInv(fact[i]);
}
int ncr(int n,int r){
	if(n<r||n<0||r<0)
		return 0;
	int b=inv[n-r];
	int c=inv[r];
	int a=fact[n]*b;
	if(a>=MOD)
		a%=MOD;
	a*=c;
	if(a>=MOD)
		a%=MOD;
	return a;
}
bool isPrime(int n) 
{ 
    // Corner case 
    if (n <= 1) 
        return false; 
  
    // Check from 2 to n-1 
    for (int i = 2; i*i<= n; i++) 
        if (n % i == 0) 
            return false; 
  
    return true; 
}
int countDigit(long long n)
{
    int count = 0;
    while (n != 0)
    {
        n = n / 10;
        ++count;
    }
    return count;
}
void solve() {
 
  int n;
  cin>>n;
  
  string s;
  cin>>s;
  
  int pre[n];
  int c=0;
  pre[0]=0;
  if(s[0]=='*')c++;
  for(int i=1;i<n;i++){
      if(s[i]=='*')
      {
          pre[i]=pre[i-1];
          c++;
          
      }
      else{
          pre[i]=pre[i-1]+c;
      }
  }
  
  int suf[n];
  suf[n-1]=0;
  
  c=0;
  if(s[n-1]=='*')c++;
  for(int i=n-2;i>=0;i--){
       if(s[i]=='*')
      {
          suf[i]=suf[i+1];
          c++;
          
      }
      else{
          suf[i]=suf[i+1]+c;
      }
  }
  int ans=min(suf[0],pre[n-1]);
  
  /*for(int i=0;i<n;i++)cout<<suf[i]<<" ";
  cout<<"\n";*/
  for(int i=0;i<n-1;i++){
     ans=min(ans,pre[i]+suf[i+1]);
  }
  
  
  cout<<ans<<"\n";
}

int32_t main()
{ 
      ios;
      int test;
      
     
      test=1;
      int cas=1;
     factorial(N-1);
      InvFactorial(N-1);
     // sieve();
    
     
      cin>>test;
      while(test--)
      {
         //cout<<"Case #"<<cas<<": ";
         solve();
         cas++;
       
        }
   
 
 
       
    
    return 0;
}
```