t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if sum(a) % 3 == 0:
        print("1 2")
    else:
        print("0 0")

#include<bits/stdc++.h>
 
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    vector<int> p(n);
    vector<int> pos0;
    vector<int> used(n);
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
        --p[i];
        if(p[i] == -1)
            pos0.push_back(i);
        else
            used[p[i]] = 1;
    }
    if(pos0.size() == 1) 
    {
        int unused = 0;
        for(int i = 0; i < n; i++) if(used[i] == 0) unused = i;
        p[pos0[0]] = unused;
    }
    int l = 0, r = n - 1;
    while(l < n && p[l] == l) l++;
    while(r >= 0 && p[r] == r) r--;
    cout << max(0, r - l + 1) << "\n";
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    int ans = 1;
    for (int i = 0; i < n; ++i) {
      if (a[i] > b[i]) swap(a[i], b[i]);
      if (!i || a[i] >= b[i - 1]) ans = (ans * 2LL) % MOD;
    }
    cout << ans << '\n';
  }
}

for _t in range(int(input())):
    n, y = map(int, input().split())
    a = list(map(int, input().split()))
    A = max(a) + 1
    cntTags = [0] * A
    for v in a:
        cntTags[v] += 1
    pSum = [0] * A
    for i in range(1, A):
        pSum[i] = pSum[i - 1] + cntTags[i]
    
    ans = -(10**18)
    if A == 2:
        print(n)
        continue
    for x in range(2, A):
        res = 0
        for price in range(1, A):
            l = x * (price - 1)
            r = min(A - 1, x * price)
            if l >= A:
                break
            cnt = pSum[r] - pSum[l]
            res += cnt * price
            res -= y * max(0, cnt - cntTags[price])
        ans = max(ans, res)
    print(ans)

#include<bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
const int N = 1000043;
 
int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}
 
int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}   
 
int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}
 
vector<int> get(const vector<int>& a)
{
    int cur = -1;
    vector<int> res;
    for(auto x : a)
        if(x > cur)
        {
            res.push_back(x);
            cur = x;
        }
    return res;
}
 
struct SegTree
{
    vector<int> f;
    vector<int> t;
    int n;
 
    int getVal(int v, int pos)
    {
        return mul(t[pos], binpow(2, f[v]));
    }   
 
    void push(int v)
    {
        if(f[v] != 0)
        {
            f[2 * v + 1] += f[v];
            f[2 * v + 2] += f[v];
            f[v] = 0;
        }
    }
 
    void resolve(int v, int pos)
    {
        if(f[v] != 0)
        {
            t[pos] = mul(t[pos], binpow(2, f[v]));
            f[v] = 0;    
        }
    }
 
    int get(int v, int l, int r, int pos)
    {
        if(l == r - 1)
            return getVal(v, pos);
        else
        {
            push(v);
            int m = (l + r) / 2;
            if(pos < m)
                return get(v * 2 + 1, l, m, pos);
            else
                return get(v * 2 + 2, m, r, pos);
        }
    }
 
    int get(int pos)
    {
        return get(0, 0, n, pos);
    }
 
    void inc(int v, int l, int r, int pos, int val)
    {
        if(l == r - 1)
        {
            resolve(v, pos);
            t[pos] = add(t[pos], val);
        }
        else
        {
            push(v);
            int m = (l + r) / 2;
            if(pos < m)
                inc(v * 2 + 1, l, m, pos, val);
            else
                inc(v * 2 + 2, m, r, pos, val);
        }
    }
 
    void inc(int pos, int val)
    {
        return inc(0, 0, n, pos, val);
    }
 
    void mulBy2(int v, int l, int r, int L, int R)
    {
        if(L >= R) return;
        if(l == L && r == R)
            f[v]++;
        else
        {
            push(v);
            int m = (l + r) / 2;
            mulBy2(v * 2 + 1, l, m, L, min(R, m));
            mulBy2(v * 2 + 2, m, r, max(L, m), R);
        }
    }
 
    void mulBy2(int l, int r)
    {
        mulBy2(0, 0, n, l, r);   
    }
 
    SegTree(int n = 0)
    {
        this->n = n;
        f.resize(4 * n);
        t.resize(n);
    }
};
 
vector<int> calc(const vector<int>& a, const vector<int>& b)
{
    int n = a.size();
    int m = b.size();
    SegTree tree(m + 1);
    tree.inc(0, 1);
    vector<int> res(n);
    int maxVal = b.back();
    for(int i = 0; i < n; i++)
    {
        int x = a[i];
        if(x > maxVal) continue;
        else
        {
            if (x == maxVal) res[i] = tree.get(m - 1);
            int lf = lower_bound(b.begin(), b.end(), x) - b.begin();
            tree.mulBy2(lf + 1, m + 1);
            if(b[lf] == x)
            {
                int cur = tree.get(lf);
                tree.inc(lf + 1, cur);
            }
        }
    }
    return res; 
}   
 
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    auto left_view = get(a);
    reverse(a.begin(), a.end());
    auto right_view = get(a);
    reverse(a.begin(), a.end());
 
    auto dpL = calc(a, left_view);
    reverse(a.begin(), a.end());
    auto dpR = calc(a, right_view);
    reverse(a.begin(), a.end());
    reverse(dpR.begin(), dpR.end());
 
    int maxVal = *max_element(a.begin(), a.end());
    int ans = 0;
    int sumLeft = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i] > maxVal) continue;
        else
        {   
            if(a[i] == maxVal) ans = add(ans, mul(add(sumLeft, dpL[i]), dpR[i]));
            sumLeft = mul(sumLeft, 2);
            if(a[i] == maxVal) sumLeft = add(sumLeft, dpL[i]);
        }
    }
    cout << ans << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);    
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) solve();
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const string al = "()";
 
struct aho_corasick {
    static const int AL = 2;
 
    struct node {
        int nxt[AL], go[AL];
        int p, pch;
        int suf, ssuf;
        bool term;
        
        node() {
            memset(nxt, -1, sizeof(nxt));
            memset(go, -1, sizeof(go));
            suf = ssuf = -1;
            term = false;
        }
    };
 
    vector<node> nodes;
    vector<vector<int>> g;
    
    aho_corasick() {
        nodes.push_back(node());
    }
 
    void add(const string& s) {
        int v = 0;
        forn(i, s.size()) {
            int c = al.find(s[i]);
            if (nodes[v].nxt[c] == -1) {
                nodes.push_back(node());
                nodes[v].nxt[c] = nodes.size() - 1;
                nodes.back().p = v;
                nodes.back().pch = c;
            }
            v = nodes[v].nxt[c];
        }
        nodes[v].term = true;
    }
    
    int go(int v, int c) {
        if (nodes[v].go[c] != -1)
            return nodes[v].go[c];
        if (nodes[v].nxt[c] != -1)
            return nodes[v].go[c] = nodes[v].nxt[c];
        if (v == 0)
            return nodes[v].go[c] = 0;
        return nodes[v].go[c] = go(suf(v), c);
    }
    
    int suf(int v) {
        if (nodes[v].suf != -1)
            return nodes[v].suf;
        if (v == 0 || nodes[v].p == 0)
            return nodes[v].suf = 0;
        return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
    }
    
    int ssuf(int v) {
        if (nodes[v].ssuf != -1)
            return nodes[v].ssuf;
        if (v == 0 || nodes[v].p == 0)
            return nodes[v].ssuf = 0;
        int s = suf(v);
        if (nodes[s].term)
            return nodes[v].ssuf = s;
        return nodes[v].ssuf = ssuf(s);
    }
    
    void build_tree() {
        g.resize(nodes.size());
        forn(v, nodes.size()) {
            int u = suf(v);
            if (v != u)
                g[u].push_back(v);
        }
    }
};
 
int main() {
    int n, k;
    cin >> n >> k;
    vector<string> s(n);
    forn(i, n) cin >> s[i];
    forn(i, n) if (s[i] == "()"){
        cout << -1 << '\n';
        return 0;
    }
    aho_corasick ac;
    forn(i, n) ac.add(s[i]);
    vector<vector<vector<char>>> dp(k + 1, vector<vector<char>>(ac.nodes.size(), vector<char>(k + 1)));
    vector<vector<vector<pair<int, int>>>> p(k + 1, vector<vector<pair<int, int>>>(ac.nodes.size(), vector<pair<int, int>>(k + 1)));
    dp[0][0][0] = true;
    forn(i, k) forn(v, ac.nodes.size()) forn(bal, i + 1) if (dp[i][v][bal]){
        forn(c, 2){
            int nbal = bal + (c == 0 ? 1 : -1);
            if (nbal < 0) continue;
            int u = ac.go(v, c);
            if (ac.nodes[u].term || ac.ssuf(u) != 0) continue;
            dp[i + 1][u][nbal] = true;
            p[i + 1][u][nbal] = {v, c};
        }
    }
    int sv = -1;
    forn(v, ac.nodes.size()) if (dp[k][v][0]){
        sv = v;
        break;
    }
    if (sv == -1){
        cout << 2 << '\n';
        vector<string> res(2);
        forn(i, k / 2){
            res[0] += "()";
            res[1] += '(';
        }
        forn(i, k / 2){
            res[1] += ')';
        }
        vector<vector<int>> ans(2);
        forn(i, n){
            bool any = false;
            forn(j, int(s[i].size()) - 1)
                any |= s[i][j] == s[i][j + 1];
            ans[!any].push_back(i);
        }
        forn(i, 2){
            cout << res[i] << '\n';
            cout << ans[i].size() << '\n';
            for (int j : ans[i]) cout << j + 1 << " ";
            cout << '\n';
        }
    }
    else{
        cout << 1 << '\n';
        string res = "";
        int bal = 0, v = sv;
        for (int i = k; i > 0; --i){
            auto [u, c] = p[i][v][bal];
            v = u;
            res += al[c];
            bal -= c == 0 ? 1 : -1;
        }
        reverse(res.begin(), res.end());
        cout << res << '\n';
        cout << n << '\n';
        forn(i, n) cout << i + 1 << " ";
        cout << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const string al = "()";
 
int main() {
    int n, k;
    cin >> n >> k;
    vector<string> s(n);
    forn(i, n) cin >> s[i];
    forn(i, n) if (s[i] == "()"){
        cout << -1 << '\n';
        return 0;
    }
 
    vector<string> ac(1, "");
    forn(i, n) forn(j, s[i].size())
        ac.push_back(s[i].substr(0, j + 1));
    sort(ac.begin(), ac.end());
    ac.resize(unique(ac.begin(), ac.end()) - ac.begin());
 
    vector<char> bad(ac.size());
    set<string> tot(s.begin(), s.end());
    vector<vector<int>> go(ac.size(), vector<int>(2));
    forn(i, ac.size()) forn(j, ac[i].size() + 1){
        bad[i] |= tot.count(ac[i].substr(j));
        forn(t, 2) if (go[i][t] == 0){
            string nw = ac[i].substr(j) + al[t];
            auto it = lower_bound(ac.begin(), ac.end(), nw);
            if (it != ac.end() && *it == nw)
                go[i][t] = it - ac.begin();
        }
    }
 
    vector<vector<vector<char>>> dp(k + 1, vector<vector<char>>(ac.size(), vector<char>(k + 1)));
    vector<vector<vector<pair<int, int>>>> p(k + 1, vector<vector<pair<int, int>>>(ac.size(), vector<pair<int, int>>(k + 1)));
    dp[0][0][0] = true;
    forn(i, k) forn(v, ac.size()) forn(bal, i + 1) if (dp[i][v][bal]){
        forn(c, 2){
            int nbal = bal + (c == 0 ? 1 : -1);
            if (nbal < 0) continue;
            int u = go[v][c];
            if (bad[u]) continue;
            dp[i + 1][u][nbal] = true;
            p[i + 1][u][nbal] = {v, c};
        }
    }
    int sv = -1;
    forn(v, ac.size()) if (dp[k][v][0]){
        sv = v;
        break;
    }
    if (sv == -1){
        cout << 2 << '\n';
        vector<string> res(2);
        forn(i, k / 2){
            res[0] += "()";
            res[1] += '(';
        }
        forn(i, k / 2){
            res[1] += ')';
        }
        vector<vector<int>> ans(2);
        forn(i, n){
            bool any = false;
            forn(j, int(s[i].size()) - 1)
                any |= s[i][j] == s[i][j + 1];
            ans[!any].push_back(i);
        }
        forn(i, 2){
            cout << res[i] << '\n';
            cout << ans[i].size() << '\n';
            for (int j : ans[i]) cout << j + 1 << " ";
            cout << '\n';
        }
    }
    else{
        cout << 1 << '\n';
        string res = "";
        int bal = 0, v = sv;
        for (int i = k; i > 0; --i){
            auto [u, c] = p[i][v][bal];
            v = u;
            res += al[c];
            bal -= c == 0 ? 1 : -1;
        }
        reverse(res.begin(), res.end());
        cout << res << '\n';
        cout << n << '\n';
        forn(i, n) cout << i + 1 << " ";
        cout << '\n';
    }
    return 0;
}