#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void I_love_feblokas();

int32_t main() {
    int32_t tc = 1;
    cin >> tc;
    while (tc-->0) {
        I_love_feblokas();
    }
    return 0;
}

void I_love_feblokas() {
    int32_t ans = 0, cnt = 0;
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (auto &c : s) {
        if (c == '*') {
            cnt = 0;
        } else {
            cnt++;
        }
        ans = max(ans, (cnt + 1) / 2);
    }
    cout << ans << '\n';
    return;
}

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void I_love_feblokas();

int32_t main() {
    int32_t tc = 1;
    cin >> tc;
    while (tc-- > 0) {
        I_love_feblokas();
    }
    return 0;
}

void I_love_feblokas() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    ll cur = 0;
    bool ok = true;
    for (ll i = 0; i < n; ++i) {
        cur += a[i];
        ll need = (i + 1) * (i + 2) / 2;
        if (cur < need) {
            ok = false;
        }
    }
    if (ok) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void I_love_feblokas();

int32_t main() {
    int32_t tc = 1;
    cin >> tc;
    while (tc-- > 0) {
        I_love_feblokas();
    }
    return 0;
}

void I_love_feblokas() {
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> p(n);
    for (auto &val : p) cin >> val;
    
    int g = gcd(x, y);
    bool ok = true;
    
    for (int i = 0; i < n; ++i) {
        if ((p[i] % g) != ((i + 1) % g)) {
            ok = false;
            break;
        }
    }
    
    if (ok) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void I_love_feblokas();

int32_t main() {
    int32_t tc = 1;
    cin >> tc;
    while (tc-->0) {
        I_love_feblokas();
    }
    return 0;
}

void I_love_feblokas() {
    int n, m;
    ll ans = 0;
    cin >> n >> m;
    vector<ll> a(n), b(m);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    b.push_back(0);
    sort(b.begin(), b.end());
    vector<ll> pref(n + 1);
    for (ll i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + a[i];
    }
    for (ll i = 1; i < b.size(); ++i) {
        ans += abs(pref[b[i]] - pref[b[i - 1]]);
    }
    ans += pref[n] - pref[b.back()];
    cout << ans << '\n';
    return;
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> pref(n, 0);
    for (int i = 0; i < n &mdash; 1; ++i) {
        pref[i + 1] = pref[i] + (s[i] == s[i + 1] ? 1 : 0);
    }
    for (int i = 0; i < q; ++i) {
        int l, r, k;
        cin >> l >> r >> k;
        if (l == r) {
            cout << "YES\n";
            continue;
        }
        int c = pref[r &mdash; 1] &mdash; pref[l &mdash; 1];
        int needed = (c + 1) / 2;
        if (needed <= k) cout << "YES\n";
        else cout << "NO\n";
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

vector<vector<int>> g;
vector<int> leaf;
bool ok;

void I_love_feblokas();
pair<int, int> dfs(int u, int p);

int32_t main() {
    int32_t tc = 1;
    cin >> tc;
    while (tc-- > 0) {
        I_love_feblokas();
    }
    return 0;
}

pair<int, int> dfs(int u, int p) {
    if (!ok) return {0, 0};
    if (leaf[u] != 0) {
        for (int v : g[u]) {
            if (v != p) {
                ok = false;
                return {0, 0};
            }
        }
        return {leaf[u], leaf[u]};
    }
    vector<pair<int, int>> segs;
    for (int v : g[u]) {
        if (v != p) {
            segs.push_back(dfs(v, u));
            if (!ok) return {0, 0};
        }
    }
    if (segs.empty()) {
        ok = false;
        return {0, 0};
    }
    vector<pair<int, int>> sorted_segs = segs;
    sort(sorted_segs.begin(), sorted_segs.end());
    for (size_t i = 0; i < sorted_segs.size() &mdash; 1; ++i) {
        if (sorted_segs[i].second + 1 != sorted_segs[i + 1].first) {
            ok = false;
            return {0, 0};
        }
    }
    int start_pos = -1;
    for (size_t i = 0; i < segs.size(); ++i) {
        if (segs[i] == sorted_segs[0]) {
            start_pos = i;
            break;
        }
    }
    if (start_pos == -1) {
        ok = false;
        return {0, 0};
    }
    for (size_t i = 0; i < segs.size(); ++i) {
        if (segs[(start_pos + i) % segs.size()] != sorted_segs[i]) {
            ok = false;
            return {0, 0};
        }
    }
    return {sorted_segs[0].first, sorted_segs.back().second};
}

void I_love_feblokas() {
    int n;
    cin >> n;
    g.assign(n + 1, vector<int>());
    leaf.assign(n + 1, 0);
    ok = true;
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        g[p].push_back(i);
        g[i].push_back(p);
    }
    int k = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> leaf[i];
        k = max(k, leaf[i]);
    }
    if (n == 1) {
        cout << "YES\n";
        return;
    }
    pair<int, int> res = dfs(1, -1);
    if (ok && res.first == 1 && res.second == k) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Fenwick {
    int n;
    vector<ll> t;
    
    Fenwick(int n) : n(n), t(n + 1, 0ll) {}
    
    int f(int x) {
        return x & -x;
    }
    
    void upd(int pos, ll val) {
        for (; pos <= n; pos += f(pos)) t[pos] = max(t[pos], val);
    }
    
    ll get(int pos) {
        ll ans = 0;
        for (; pos > 0; pos -= f(pos)) ans = max(ans, t[pos]);
        return ans;
    }
};

void I_love_feblokas() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    Fenwick t(n);
    vector<vector<pair<int, ll>>> ev(n + 1);
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (auto& ev : ev[i]) {
            t.upd(ev.first, ev.second);
        }
        int lim = i - a[i] - 1;
        ll mx = 0;
        if (lim > 0) {
            mx = t.get(min(n, lim));
        }
        ll dp_i = a[i] + mx;
        ans = max(ans, dp_i);
        ll act = i + a[i] + 1;
        if (act <= n) {
            ev[act].push_back({i, dp_i});
        }
    }
    cout << ans << "\n";
}

int main() {
    int t;
    cin >> t ;
    while (t--) {
        I_love_feblokas();
    }
    return 0;
}