1520E - Arranging The Sheep - CodeForces Solution

//#pragma GCC optimize("O2,unroll-loops,fast-math")
//#pragma GCC target("avx,avx2,sse,sse2,sse3")
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ll long long
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define fi first
#define se second
void chkmx(int& a, int b) {
    a = max(a, b);
}
void chkmn(int& a, int b) {
    a = min(a, b);
}
void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> pos;
    for (int i = 0 ; i < n; ++i) {
        if (s[i] == '*')
            pos.emplace_back(i);
    }
    int psz = pos.size();
    vector<int> dpr(psz), dsu(psz);
    for (int i = 1; i < psz; ++i) {
        dpr[i] = dpr[i-1] + i * (pos[i]-1 - pos[i-1]);
    }
    for (int i = psz-2; i >= 0; --i) {
        dsu[i] = dsu[i+1] + (psz-1 - i) * (pos[i+1]-pos[i]-1);
    }
    int ans = 1e18;
    for (int i = 0; i < n; ++i) {
        int pl = lower_bound(all(pos), i) - pos.begin() - 1;
        int pr = pl+1;
        int pref, suf;
        // i-1 i
        if (pl == -1)
            pref = 0;
        else
            pref = max(0ll, i-1 - pos[pl]) * (pl+1) + dpr[pl];
        if (pr == psz)
            suf = 0;
        else
            suf = max(0ll, pos[pr] - i) * (psz - pr) + dsu[pr];
        chkmn(ans, pref + suf);
    }
    cout << ans << '\n';
}
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    if (fopen("input.txt", "r")) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    int tests = 1;
    cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}