#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int x = 10000, y = 0;
        for (int i = 0; i < n; ++i) {
            int z;
            cin >> z;
            x = min(x, z), y += x;
        }
        cout << y << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n), c(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        set<int> s;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            s.insert(x);
        }
        bool y = true;
        for (int i = 0; i < n; ++i) {
            auto it = s.lower_bound(a[i]);
            if (it == s.end()) {
                y = false;
                break;
            }
            c[i] = *it;
            s.erase(it);
        }
        if (!y) {
            cout << -1 << '\n';
            continue;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (c[i] > c[j]) {
                    ans++;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

void run() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    i64 ans = 0;
    for (int i = 0; i < n; ++i) {
        if (ans > a[i]) {
            ans += a[i];
        } else {
            ans = a[i];
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        run();
    }
    return 0;
}

for _ in range(int(input())):
    n = int(input())
    a = [1, 0, 0]
    x = 0
    ans = 0
    pre = ""
    y = 0
    for c in input():
        if c == "0":
            x -= 1
        else:
            x += 1
        x %= 3
        if c == pre:
            y = 1
        else:
            y += 1
        pre = c
        ans += sum(a) - a[x]
        a[x] += 1
        ans -= (y - 1) // 2
    print(ans)

#include <bits/stdc++.h>

using namespace std;


void run(int testCase) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        if (b[i] != -1) {
            b[i]--;
        }
    }
    vector<int> vis(n);
    for (int i = 0; i < n; ++i) {
        if (b[i] != -1 and !vis[i]) {
            int j = i;
            while (true) {
                if (vis[j]) break;
                vis[j] = 1;
                if (b[a[j]] == -1) {
                    b[a[j]] = a[b[j]];
                } else if (b[a[j]] != a[b[j]]) {
                    cout << "NO\n";
                    return;
                }
                j = a[j];
            }
        }
    }
    vector<int> cnt(n);
    for (int i = 0; i < n; ++i) {
        if (b[i] == -1) continue;
        cnt[b[i]]++;
    }
    for (int i = 0; i < n; ++i) {
        if (cnt[i] > 1) {
            cout << "NO\n";
            return;
        }
    }
    vector<int> vis1(n), vis2(n);
    vector<vector<int>> cycle1(n + 1), cycle2(n + 1);
    for (int i = 0; i < n; ++i) {
        if (b[i] == -1 and !vis1[i]) {
            int j = i, len = 0;
            while (!vis1[j]) {
                vis1[j] = 1;
                len++;
                j = a[j];
            }
            cycle1[len].push_back(i);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (cnt[i] == 0 and !vis2[i]) {
            int j = i, len = 0;
            while (!vis2[j]) {
                vis2[j] = 1;
                len++;
                j = a[j];
            }
            cycle2[len].push_back(i);
        }
    }
    for (int len = 1; len <= n; ++len) {
        for (int i = 0; i < cycle1[len].size(); ++i) {
            int x = cycle1[len][i], y = cycle2[len][i];
            while (b[x] == -1) {
                b[x] = y;
                x = a[x];
                y = a[y];
            }
        }
    }
    cout << "YES\n";
    for (int i = 0; i < n; ++i) {
        cout << b[i] + 1 << " \n"[i == n - 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        run(t);
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
int a[500000], pref[500001], suf[500001], dpvl[500001], inf = 1000000000;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T, n, m, i, c;
    for (cin >> T; T > 0; T--) {
        cin >> n >> m;
        for (i = 0; i < n; i++) {
            cin >> a[i];
            a[i]--;
        }
        for (i = 0; i <= n; i++) {
            pref[i] = -inf;
            suf[i] = -inf;
            dpvl[i] = -inf;
        }
        pref[0] = 0;
        for (i = 0; i < n; i++) {
            c = suf[i];
            if (i - a[i] >= 0) {
                c = max(c, dpvl[i - a[i]]);
                c = max(c, pref[i - a[i]]);
            }
            c++;
            pref[i + 1] = max(pref[i], c);
            suf[i + 1] = max(suf[i + 1], suf[i]);
            if (i - a[i] >= 0)dpvl[i - a[i]] = max(dpvl[i - a[i]], c);
            if (i - a[i] + m <= n)suf[i - a[i] + m] = max(suf[i - a[i] + m], c);
        }
        cout << n - max(suf[n], 0) << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>

#define sz(a) (int)(a).size()

using namespace std;

using i64 = long long;

string type;

constexpr int P = 110;
constexpr int N = 1e6;
constexpr int sz_v = (1 << 18);

vector<int> ps, pks, v;
array<int, N + 1> idx;

void init() {
    vector<int> max_p(N + 1);
    max_p[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (max_p[i] == 0) {
            ps.push_back(i);
            for (int j = i; j <= N; j += i) {
                max_p[j] = i;
            }
        }
    }
    ps.resize(P);
    for (int p: ps) {
        int x = p;
        while (x * p <= N) x *= p;
        pks.push_back(x);
    }
    for (int i = 1; i <= N and sz(v) < sz_v; ++i) {
        if (max_p[i] <= ps.back()) {
            v.push_back(i);
        }
    }
    assert(sz(v) == sz_v);
    for (int i = 0; i < sz(v); ++i) idx[v[i]] = i;
}


void run1() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> b;
    for (int pk: pks) b.push_back(pk);
    vector<int> bits;
    for (int i = 0; i < n; ++i) {
        for (int j = 19; j >= 0; --j) {
            bits.push_back(a[i] >> j & 1);
        }
    }
    while (sz(bits) % 18) bits.push_back(0);
    for (int i = 0; i < sz(bits); i += 18) {
        int now = 0;
        for (int j = 0; j < 18; ++j) {
            now *= 2;
            now += bits[i + j];
        }
        b.push_back(v[now]);
    }
    int k = sz(b);
    cout << k << '\n';
    for (int i = 0; i < k; ++i) cout << b[i] << ' ';
    cout << '\n';
}

void run2() {
    int n, k;
    cin >> n >> k;
    auto ask = [&](int i, int j) {
        assert(i != j);
        cout << "? " << i + 1 << ' ' << j + 1 << endl;
        int g;
        cin >> g;
        return g;
    };
    vector<int> bits;
    for (int i = P; i < k; ++i) {
        int x = 1;
        for (int j = 0; j < P; ++j) {
            int g = ask(i, j);
            x *= g;
        }
        int now = idx[x];
        for (int j = 17; j >= 0; --j) {
            bits.push_back(now >> j & 1);
        }
    }
    vector<int> a(n);
    for (int i = 0, j = 0; i < n; ++i, j += 20) {
        int now = 0;
        for (int x = 0; x < 20; ++x) {
            now *= 2;
            now += bits[j + x];
        }
        a[i] = now;
    }
    cout << "!";
    for (int i = 0; i < n; ++i) cout << ' ' << a[i];
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    cin >> type;
    int T = 1;
    cin >> T;
    while (T--) {
        if (type == "first") {
            run1();
        } else {
            run2();
        }
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
vector<int> line[100000];
int dfn[100000], siz[100000], fa[100000], wp[100000], tp[100000], dep[100000], cdfn;

void dfs1(int t, int f) {
    vector<int>::iterator it;
    int mx = -1;
    fa[t] = f;
    siz[t] = 1;
    wp[t] = -1;
    for (it = line[t].begin(); it != line[t].end(); it++) {
        if ((*it) == f)continue;
        dep[*it] = dep[t] + 1;
        dfs1(*it, t);
        siz[t] += siz[*it];
        if (siz[*it] > mx) {
            mx = siz[*it];
            wp[t] = *it;
        }
    }
}

void dfs2(int t, int f) {
    vector<int>::iterator it;
    dfn[t] = cdfn;
    cdfn++;
    if (wp[t] == -1)return;
    tp[wp[t]] = tp[t];
    dfs2(wp[t], t);
    for (it = line[t].begin(); it != line[t].end(); it++) {
        if ((*it) == f)continue;
        if (*it == wp[t])continue;
        tp[*it] = *it;
        dfs2(*it, t);
    }
}

map<int, int> mp, sg;

void access(int p) {
    map<int, int>::iterator it;
    int x;
    it = sg.upper_bound(p);
    it--;
    x = (*it).second;
    sg[p] = x;
}

int chkmap(int c, int vl) {
    map<int, int>::iterator it;
    int d;
    while (1) {
        it = mp.upper_bound(vl);
        if (it == mp.begin())break;
        it--;
        d = min((*it).second, c);
        c -= d;
        (*it).second -= d;
        if ((*it).second == 0)mp.erase(it);
        if (c == 0)break;
    }
    return c;
}

int upd(int l, int r, int p) {
    int ans = 0, lst, lvl;
    map<int, int>::iterator it;
    access(l);
    access(r);
    lst = l;
    lvl = sg[l];
    while (1) {
        it = sg.upper_bound(l);
        ans += chkmap((*it).first - lst, lvl);
        lst = (*it).first;
        lvl = (*it).second;
        if ((*it).first == r)break;
        sg.erase(it);
    }
    sg[l] = p;
    mp[p] += r - l - ans;
    return ans;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T, n, m, q, i, u, v, p;
    long long ans;
    for (cin >> T; T > 0; T--) {
        cin >> n >> m >> q;
        for (i = 0; i < n - 1; i++) {
            cin >> u >> v;
            line[u - 1].push_back(v - 1);
            line[v - 1].push_back(u - 1);
        }
        dep[0] = 0;
        dfs1(0, -1);
        cdfn = 0;
        tp[0] = 0;
        dfs2(0, -1);
        sg[0] = -1;
        sg[n] = -1;
        for (i = 0; i < m; i++) {
            cin >> p;
            p--;
            access(dfn[p] + 1);
            sg[dfn[p]] = 0;
        }
        mp[0] = m;
        ans = 0;
        for (i = 1; i <= q; i++) {
            u = p;
            cin >> p;
            p--;
            p = (p + ans) % n;
            v = p;
            while (1) {
                if (tp[u] == tp[v]) {
                    if (dep[v] > dep[u])swap(u, v);
                    ans += upd(dfn[v], dfn[u] + 1, i);
                    break;
                }
                if (dep[tp[v]] > dep[tp[u]])swap(u, v);
                ans += upd(dfn[tp[u]], dfn[u] + 1, i);
                u = fa[tp[u]];
            }
            cout << ans << ' ';
        }
        cout << '\n';
        for (i = 0; i < n; i++)line[i].clear();
        mp.clear();
        sg.clear();
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
const long long mod = 1000000007;
vector<int> line[3000];
string s;
long long dp[4][3000][3001], dpc[4][3000][3001], tdp[4][3001], tdpc[4][3001];
int dep[3000], vis1[3000], vislink[3000];

void merge(int u, int v, int pu, int pv, int pt) {
    int i, j;
    for (i = 0; i <= dep[u]; i++) {
        for (j = 0; j <= dep[v]; j++) {
            tdp[pt][max(i, j)] = (tdp[pt][max(i, j)] + dp[pu][u][i] * dp[pv][v][j]) % mod;
            if (i <= j)tdpc[pt][j] = (tdpc[pt][j] + dp[pu][u][i] * dpc[pv][v][j]) % mod;
            if (i > j)tdpc[pt][i] = (tdpc[pt][i] + dpc[pu][u][i] * dp[pv][v][j]) % mod;
        }
    }
}

void dfs(int t) {
    vector<int>::iterator it;
    int i, j, p, x, y, r0 = 0;
    long long vl;
    dp[0][t][0] = 1;
    dep[t] = 0;
    vis1[t] = 0;
    vislink[t] = 0;
    for (it = line[t].begin(); it != line[t].end(); it++) {
        if (s[*it] == '0')r0++;
    }
    for (it = line[t].begin(); it != line[t].end(); it++) {
        dfs(*it);
        if (s[*it] == '0')r0--;
        merge(t, *it, 0, 0, 0);
        if (s[*it] == '1') {
            merge(t, *it, 3, 1, 2);
            merge(t, *it, 3, 1, 3);
        } else {
            merge(t, *it, 2, 1, 2);
            merge(t, *it, 3, 1, 3);
        }
        if (vis1[t] == 0 && r0 == 0 && vislink[*it]) {
            if (vislink[t] == 0) {
                vislink[t] = 1;
                for (i = 0; i <= dep[*it]; i++) {
                    tdp[2][i] = (tdp[2][i] + dp[2][*it][i]) % mod;
                    tdpc[2][i] = (tdpc[2][i] + dpc[2][*it][i]) % mod;
                    tdp[3][i] = (tdp[3][i] + dp[3][*it][i]) % mod;
                    tdpc[3][i] = (tdpc[3][i] + dpc[3][*it][i]) % mod;
                }
            } else {
                for (i = 0; i <= dep[*it]; i++) {
                    tdp[2][i] = (tdp[2][i] + dp[2][*it][i]) % mod;
                    tdpc[2][i] = (tdpc[2][i] + dpc[2][*it][i]) % mod;
                    tdp[3][i] = (tdp[3][i] + dp[2][*it][i]) % mod;
                    tdpc[3][i] = (tdpc[3][i] + dpc[2][*it][i]) % mod;
                    if (s[*it] == '1') {
                        tdp[2][i] = (tdp[2][i] + dp[1][*it][i]) % mod;
                        tdpc[2][i] = (tdpc[2][i] + dpc[1][*it][i]) % mod;
                        tdp[3][i] = (tdp[3][i] + dp[1][*it][i]) % mod;
                        tdpc[3][i] = (tdpc[3][i] + dpc[1][*it][i]) % mod;
                    }
                }
            }
        }
        vis1[t] |= vis1[*it];
        dep[t] = max(dep[t], dep[*it]);
        for (p = 0; p < 4; p++) {
            for (i = 0; i <= dep[t]; i++) {
                dp[p][t][i] = tdp[p][i];
                dpc[p][t][i] = tdpc[p][i];
                tdp[p][i] = 0;
                tdpc[p][i] = 0;
            }
        }
    }
    if (s[t] == '0') {
        dep[t]++;
        return;
    }
    for (i = 0; i <= dep[t]; i++) {
        tdp[0][i + 1] = (tdp[0][i + 1] + dp[0][t][i]) % mod;
        tdpc[0][i + 1] = (tdpc[0][i + 1] + dpc[0][t][i]) % mod;
    }
    vl = 0;
    for (i = 0; i <= dep[t]; i++) {
        vl = (vl + dp[2][t][i]) % mod;
        vl = (vl + mod - dpc[2][t][i]) % mod;
    }
    tdpc[0][1] = (tdpc[0][1] + vl) % mod;
    dep[t]++;
    vislink[t] = 1;
    if (s[t] == '1') {
        vis1[t] = 1;
        for (i = 0; i <= dep[t]; i++) {
            dp[0][t][i] = tdp[0][i];
            dpc[0][t][i] = tdpc[0][i];
            dp[1][t][i] = tdp[0][i];
            dpc[1][t][i] = tdpc[0][i];
            dp[2][t][i] = 0;
            dpc[2][t][i] = 0;
            dp[3][t][i] = 0;
            dpc[3][t][i] = 0;
        }
    } else {
        for (i = 0; i <= dep[t]; i++) {
            dp[0][t][i] = (dp[0][t][i] + tdp[0][i]) % mod;
            dpc[0][t][i] = (dpc[0][t][i] + tdpc[0][i]) % mod;
            dp[1][t][i] = tdp[0][i];
            dpc[1][t][i] = tdpc[0][i];
            dp[3][t][i] = dp[2][t][i];
            dpc[3][t][i] = dpc[2][t][i];
            dp[2][t][i] = (dp[2][t][i] + tdp[0][i]) % mod;
            dpc[2][t][i] = (dpc[2][t][i] + tdpc[0][i]) % mod;
        }
    }
    for (i = 0; i <= dep[t]; i++) {
        tdp[0][i] = 0;
        tdpc[0][i] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T, n, i, j, p, c;
    long long ans;
    for (cin >> T; T > 0; T--) {
        cin >> n >> s;
        s = '1' + s;
        for (i = 0; i < n; i++) {
            cin >> c;
            for (j = 0; j < c; j++) {
                cin >> p;
                line[i].push_back(p - 1);
            }
        }
        for (p = 0; p < 4; p++) {
            for (i = 0; i < n; i++) {
                for (j = 0; j <= n; j++) {
                    dp[p][i][j] = 0;
                    dpc[p][i][j] = 0;
                }
            }
        }
        dfs(0);
        ans = 0;
        for (i = 0; i <= dep[0]; i++) {
            ans = (ans + dp[0][0][i]) % mod;
            ans = (ans + mod - dpc[0][0][i]) % mod;
        }
        cout << ans << '\n';
        for (i = 0; i < n; i++)line[i].clear();
    }
    return 0;
}