//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = -1, inf = 1000111222;

map <vector <int>, int> dp;

inline int who (vector <int> a) {
    sort(all(a));
    if (dp.count(a)) {
        return dp[a];
    }
    if (a[2] == 1) {
        return 0;
    }
    set <int> have;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == j) {
                continue;
            }
            for (int k = 1; k < a[j]; k++) {
                vector <int> c;
                int lft = 3 - i - j;
                c.pb(a[lft]);
                c.pb(k);
                c.pb(a[j] - k);
                have.insert(who(c));
            }
        }
    }
    int mn = 0;
    while (have.count(mn)) ++mn;
    return dp[a] = mn;
}

inline void test_case () {
    int n;
    cin >> n;
    vector <ll> a(n);
    int cnt[2] = {};
    for (auto &i : a) {
        cin >> i;
        ++cnt[i & 1ll];
    }
    if (cnt[1] == n) {
        cout << "0\n";
        return;
    }
    if (n % 2 == 0) {
        cout << "1\n";
        return;
    }
    if (cnt[0] && cnt[1]) {
        cout << "1\n";
        return;
    }
    cout << "0\n";
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);


    for (int a = 2; a <= 12; a += 2) {
        for (int b = a; b <= 12; b += 2) {
            for (int c = b; c <= 12; c += 2) {

                cout << a << ' ' << b << ' ' << c << ' ' << who({a, b, c}) << endl;
                /*if ((a % 4 == 2 && b % 4 == 2 && c % 4 == 2) ||
                 * "C:\Users\Acer\Desktop\Codeforces\ICPC\05 06 2023\L\cmake-build-debug\L.exe"
2 2 2 0
2 2 4 2
2 2 6 0
2 2 8 3
2 2 10 0
2 2 12 2
2 4 4 4
2 4 6 5
2 4 8 8
2 4 10 2
2 4 12 7
2 6 6 0
2 6 8 5
2 6 10 0
2 6 12 6
2 8 8 3
2 8 10 10
2 8 12 7
2 10 10 0
2 10 12 2
2 12 12 6
4 4 4 0
4 4 6 3
4 4 8 1
4 4 10 6
4 4 12 0
4 6 6 3
4 6 8 9
4 6 10 6
4 6 12 10
4 8 8 4
4 8 10 10
4 8 12 11
4 10 10 7
4 10 12 9
4 12 12 0
6 6 6 0
6 6 8 4
6 6 10 0
6 6 12 3
6 8 8 4
6 8 10 10
6 8 12 11
6 10 10 0
6 10 12 4
6 12 12 4
8 8 8 0
8 8 10 2
8 8 12 2
8 10 10 7
8 10 12 2
8 12 12 1
10 10 10 0
10 10 12 4
10 12 12 4
12 12 12 0

                    (a % 4 == 0 && b % 4 == 0 && c % 4 == 0)) {
                    assert(who({a, b, c}) == 0);
                }
                if (who({a, b, c}) == 0) {
                    if (a % 2 == 0 && b % 2 == 0 && c % 2 == 0) {
                        assert((a % 4 == 2 && b % 4 == 2 && c % 4 == 2) ||
                               (a % 4 == 0 && b % 4 == 0 && c % 4 == 0));
                    }
                }*/
            }
        }
    }
    int t = 1;
    cin >> t;
    for (int test = 1; test <= t; test++) {
        test_case();
    }
}