#include <bits/stdc++.h>
 
using namespace std;
 
signed main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
 
    int t;
    cin >> t;
    for(int _ = 0; _ < t; ++_){
        int n, ans = 0;
        cin >> n;
        string s;
        cin >> s;
        for (int i = 1; i < n; i++) {
            ans += (s[i] == '@');
            if (s[i] == '*' && s[i - 1] == '*')
                break;
        }
        cout << ans << "\n";
    }
    return 0;
}

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    cur = 0
    for e in a:
        cur += e - cur % e
    print(cur)
 
 
for _ in range(1, int(input()) + 1):
    solve()

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];
        string s;
        cin >> s;
 
        int l = 0;
        int r = n - 1;
        forn(i, n - 1)
            if (s[i] == 'L')
                l++;
            else
                r--;
        assert(l == r);
 
        vector<int> b(n);
        b[n - 1] = a[l] % m;
 
        for (int i = n - 2; i >= 0; i--) {
            if (s[i] == 'L')
                b[i] = (b[i + 1] * a[--l]) % m;
            else
                b[i] = (b[i + 1] * a[++r]) % m;
        }
        assert(l == 0);
        assert(r == n - 1);
 
        forn(i, n)
            cout << b[i] << " ";
        cout << endl;
    }
}

#include <bits/stdc++.h>
 
#define long long long int
#define DEBUG
using namespace std;
 
// @author: pashka
 
int main() {
    ios::sync_with_stdio(false);
    
    int t;
    cin >> t;
    for (int tt = 0; tt < t; tt++) {
        int n;
        cin >> n;
    
        string suites = "CDHS";
    
        string ts;
        cin >> ts;
        int trump = suites.find(ts[0]);
    
        vector<int> bs[4];
        for (int i = 0; i < 2 * n; i++) {
            string s;
            cin >> s;
            bs[suites.find(s[1])].push_back(s[0] - '2');
        }
    
        vector<string> res;
        vector<string> left;
        for (int i = 0; i < 4; i++) {
            sort(bs[i].begin(), bs[i].end());
            if (i == trump) continue;
            if (bs[i].size() % 2 == 1) {
                int x = bs[i].back();
                left.push_back(string() + char('2' + x) + suites[i]);
                bs[i].pop_back();
            }
            for (int j = 0; j < (int) bs[i].size(); j++) {
                int x = bs[i][j];
                res.push_back(string() + char('2' + x) + suites[i]);
            }
        }
        if (left.size() > bs[trump].size()) {
            cout << "IMPOSSIBLE\n";
        } else {
            for (string s : left) {
                res.push_back(s);
                int x = bs[trump].back();
                bs[trump].pop_back();
                res.push_back(string() + char('2' + x) + suites[trump]);
            }
            for (int j = 0; j < (int) bs[trump].size(); j++) {
                int x = bs[trump][j];
                res.push_back(string() + char('2' + x) + suites[trump]);
            }
            for (int i = 0; i < 2 * n; i += 2) {
                cout << res[i] << " " << res[i + 1] << "\n";
            }
        }
    }
}

#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
 
// @author: pashka
 
int main() {
    ios::sync_with_stdio(false);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        reverse(s.begin(), s.end());
        vector<int> a(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            a[i] = a[i + 1] + (s[i] - '0');
        }
        string res;
        int c = 0;
        for (int i = 0; i < n; i++) {
            c += a[i];
            res += (char)(c % 10 + '0');
            c /= 10;
        }
        res += (char)(c + '0');
        while (res.back() == '0') {
            res.pop_back();
        }
        reverse(res.begin(), res.end());
        cout << res << "\n";
    }
 
    return 0;
}

#include <bits/stdc++.h>
 
//#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(time(nullptr));
 
const ll inf = 1e18;
const ll M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
 
void solve(int tc){
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(m);
    vector<int> op(n + 1);
    vector<vector<int>> del(n + 1);
    for(auto &e: a) {
        cin >> e.x >> e.y;
        op[e.x]++;
        del[e.y].emplace_back(e.x);
    }
    multiset<int> cur;
    vector<int> dp(n + 1);
    for(int i = 1; i <= n; ++i){
        dp[i] = dp[i - 1];
        for(int j = 0; j < op[i]; ++j){
            cur.insert(i);
        }
        if(!cur.empty()){
            dp[i] = max(dp[i], int(dp[*cur.begin() - 1] + cur.size()));
        }
        for(int e: del[i]){
            cur.erase(cur.find(e));
        }
    }
    cout << dp[n];
}
 
bool multi = true;
 
signed main() {
    int t = 1;
    if (multi)cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
 
// @author: pashka
 
struct triple {
    long d, x, y;
};
 
triple eucl(long a, long b) {
    if (b == 0) {
        return {a, 1, 0};
    }
    long k = a / b;
    auto [d, x, y] = eucl(b, a - k * b);
    return {d, y, x - k * y};
}
 
struct test {
    void solve() {
        int n, m, H;
        cin >> n >> m >> H;
        vector<long> l(n);
        for (int i = 0; i < n; i++) cin >> l[i];
        vector<long> s(n);
        for (int i = 0; i < n; i++) cin >> s[i];
 
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            g[x].push_back(y);
            g[y].push_back(x);
        }
 
        const long INF = 1e18;
        vector<long> d(n, INF);
        d[0] = 0;
        set<pair<long, int>> q;
        q.insert({d[0], 0});
        while (!q.empty()) {
            auto p = *q.begin();
            q.erase(p);
            int v = p.second;
            long t = d[v];
            for (int u: g[v]) {
                long a = (l[v] + (t % H) * s[v]) - (l[u] + (t % H) * s[u]);
                a %= H;
                if (a < 0) a += H;
                long b = s[u] - s[v];
                b %= H;
                if (b < 0) b += H;
                // a - bx = yH
                auto [dd, x, y] = eucl(b, H);
                // xb + yH = dd
                if (a % dd != 0) continue;
                x *= a / dd;
                x %= (H / dd);
                if (x < 0) x += H / dd;
                long dt = x;
                if (d[v] + dt + 1 < d[u]) {
                    q.erase({d[u], u});
                    d[u] = d[v] + dt + 1;
                    q.insert({d[u], u});
                }
            }
        }
        long res = d[n - 1];
        if (res == INF) res = -1;
        cout << res << "\n";
    }
};
 
int main() {
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        test().solve();
    }
    
    return 0;
}