#include<bits/stdc++.h>

using namespace std;

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t, a, b, c;
    cin >> t;
    while (t--) {
        cin >> a >> b >> c;
        cout << (a + c) % 2 << '\n';
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t, n, x;
    cin >> t;
    while (t--) {
        cin >> n;
        int cnt0 = 0, cnt1 = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> x;
            if (x == 0) cnt0++;
            if (x == 1) cnt1++;
        }
        cout << (1ll << cnt0) * (ll)cnt1 << '\n';
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t, n;
    cin >> t;
    while (t--) {
        string s;
        cin >> n >> s;
        int ans = n + 1;
        for (int c = 0; c < 26; ++c) {
            int l = 0, r = n - 1, cnt = 0;
            while (l <= r) {
                if (s[l] == s[r]) {
                    l++, r--;
                }
                else if (s[l] == char('a' + c)) {
                    cnt++, l++;
                }
                else if (s[r] == char('a' + c)) {
                    cnt++, r--;
                }
                else {
                    cnt = n + 1;
                    break;
                }
            }
            ans = min(ans, cnt);
        }
        if (ans == n + 1) ans = -1;
        cout << ans << '\n';
    }
    return 0;
}

ttt = int(input())
for t in range(ttt):
	n = int(input())
	a = [int(x) for x in input().split()]
	start = 0
	if n % 2 == 1:
		if (a[0] + a[1] != 0):
			print(-a[2], -a[2], a[0] + a[1], end = " ")
		elif (a[1] + a[2] != 0):
			print(a[2] + a[1], -a[0], -a[0], end = " ")
		else:
			print(-a[1], a[0] + a[2], -a[1], end = " ")
		start = 3
	while start < n:
		print(-a[s + 1], a[s], end = " ")
		start += 2
	print()

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
int const maxn = 1e5 + 5, maxk = 450;
int a[maxn], dp[maxn][maxk];
int inf = 1e9 + 7;
ll pref[maxn];

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            pref[i] = pref[i - 1] + a[i];
        }
        int k = 0;
        while (k * (k + 1) / 2 <= n) k++;
        for (int j = 0; j < k; ++j) {
            dp[n + 1][j] = -inf;
        }
        dp[n + 1][0] = inf;
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j < k; ++j) {
                dp[i][j] = dp[i + 1][j];
                if (j && i + j - 1 <= n && pref[i + j - 1] - pref[i - 1] < dp[i + j][j - 1]) {
                    dp[i][j] = max(dp[i][j], (int)(pref[i + j - 1] - pref[i - 1]));
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < k; ++j) {
            if (dp[1][j] > 0) ans = j;
        }
        cout << ans << '\n';
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int const max_value = (1 << 13);
vector < int > g[max_value];
int ans[max_value], r[max_value];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, x;
    cin >> n;
    ans[0] = 1;
    for (int i = 0; i < max_value; ++i) {
        g[i].push_back(0);
    }
    for (int i = 0; i < max_value; ++i) {
        r[i] = max_value;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        for (auto key : g[x]) {
            int to = (key^x);
            ans[to] = 1;
            while (r[to] > x) {
                r[to]--;
                if (r[to] != x) g[r[to]].push_back(to);
            }
        }
        g[x] = {};
    }
    int k = 0;
    for (int i = 0; i < max_value; ++i) {
        k += ans[i];
    }
    cout << k << '\n';
    for (int i = 0; i < max_value; ++i) {
        if (ans[i]) cout << i << " ";
    }
    cout << '\n';
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int const maxn = 1e6 + 5;
int a[maxn];
int prime[maxn];
int L[maxn];
vector < int > pos[maxn];

inline void add(int x, int l) {
    L[l] = l;
    while (x > 1) {
        pos[prime[x]].push_back(l);
        x /= prime[x];
    }
}

inline void del(int x, int l) {
    if (x == 1) {
        L[l] = l;
        return;
    }
    L[l] = l;
    while (x > 1) {
        if ((int)pos[prime[x]].size() == 0) {
            L[l] = 0;
            return;
        }
        L[l] = min(L[l], pos[prime[x]].back());
        pos[prime[x]].pop_back();
        x /= prime[x];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 2; i < maxn; ++i) {
        if (prime[i] == 0) {
            prime[i] = i;
            if (i > 1000) continue;
            for (int j = i * i; j < maxn; j += i) {
                prime[j] = i;
            }
        }
    }

    char type;
    for (int i = 1; i <= n; ++i) {
        cin >> type;
        if (type == '*') add(a[i], i);
        else del(a[i], i);
    }

    ll answer = 0;
    vector < pair < int, int > > f_min;
    for (int i = n; i >= 1; --i) {
        int cnt = 1;
        while ((int)f_min.size() > 0 && f_min.back().first >= L[i]) {
            cnt += f_min.back().second;
            f_min.pop_back();
        }
        f_min.push_back({L[i], cnt});
        if (L[i] == i) answer += (ll)cnt;
    }
    cout << answer << '\n';
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t, n, k;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        cout << n - k + k / 2 << '\n';
        for (int i = k + 1; i <= n; ++i) cout << i << " ";
        for (int i = (k + 1) / 2; i < k; ++i) cout << i << " ";
        cout << '\n';
    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

vector < int > go = {0, 1, 5, -1, -1, 2, -1, -1, 8, -1};
int inf = 1e9 + 7;

int get(int x) {
    string s = to_string(x);
    if ((int)s.size() == 1) s = "0" + s;
    string answ = "";
    for (int i = 1; i >= 0; --i) {
        if (go[s[i] - '0'] == -1) return inf;
        answ += char(go[s[i] - '0'] + '0');
    }
    return stoi(answ);
}

string good(int x) {
    string ans = to_string(x);
    if (x < 10) {
        ans = "0" + ans;
    }
    return ans;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t, h, m, H, M;
    cin >> t;
    string s;
    while (t--) {
        cin >> h >> m;
        cin >> s;
        H = (s[0] - '0') * 10 + s[1] - '0';
        M = (s[3] - '0') * 10 + s[4] - '0';
        while (1) {
            if (M == m) {
                H++, M = 0;
            }
            if (H == h) {
                H = 0;
            }
            if (get(M) < h && get(H) < m) {
                cout << good(H) << ":" << good(M) << '\n';
                break;
            }
            M++;
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int cnt[26];

int get(int x, int k) {
    return (k - x % k) % k;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k, t;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        string s;
        cin >> s;
        for (int j = 0; j < 26; ++j) cnt[j] = 0;
        for (auto c : s) cnt[c - 'a']++;

        int sum = 0, flag = 1;
        for (int i = 0; i < 26; ++i) {
            sum += get(cnt[i], k);
        }

        if (sum == 0) {
            cout << s << '\n';
            flag = 0;
        }

        if (n % k != 0) {
            cout << -1 << '\n';
            continue;
        }

        for (int i = n - 1; i >= 0 && flag; --i) {
            sum -= get(cnt[s[i] - 'a'], k);
            cnt[s[i] - 'a']--;
            sum += get(cnt[s[i] - 'a'], k);
            for (int j = s[i] - 'a' + 1; j < 26; ++j) {

                int lst_sum = sum;
                sum -= get(cnt[j], k);
                cnt[j]++;
                sum += get(cnt[j], k);

                if (i + sum + 1 <= n) {
                    for (int pos = 0; pos < i; ++pos) {
                        cout << s[pos];
                    }
                    cout << char('a' + j);

                    string add = "";
                    for (int w = 0; w < 26; ++w) {
                        int f = get(cnt[w], k);
                        while (f) {
                            f--;
                            add += char('a' + w);
                        }
                    }
                    while ((int)add.size() + i + 1 < n) {
                        add += "a";
                    }

                    sort(add.begin(), add.end());
                    cout << add << '\n';
                    flag = 0;
                    break;
                }

                cnt[j]--;
                sum = lst_sum;
            }
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int const maxn = 2e5 + 5, max_val = 2e5 + 5;
ll mod = 1e9 + 7, ans = 1;
int nxt[max_val], n;
multiset <int> cnt[max_val];
map <int, int> cnt_divisor[maxn];

void add(int i, int x) {
    while (x != 1) {
        int div = nxt[x], add = 0;
        while (nxt[x] == div) add++, x = x / nxt[x];

        int lst = cnt_divisor[i][div];
        cnt_divisor[i][div] += add;
        int lst_min = 0;
        if ((int)cnt[div].size() == n) {
            lst_min = (*cnt[div].begin());
        }
        if (lst != 0) {
            cnt[div].erase(cnt[div].find(lst));
        }
        cnt[div].insert(lst + add);
        if ((int)cnt[div].size() == n) {
            for (int j = lst_min + 1; j <= (*cnt[div].begin()); ++j) {
                ans = ans * (ll)div % mod;
            }
        }
    }
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int q, l, x;
    cin >> n >> q;

    for (int i = 2; i < maxn; ++i) {
        if (nxt[i] == 0) {
            nxt[i] = i;
            if (i > 10000) continue;
            for (int j = i * i; j < maxn; j += i) {
                if (nxt[j] == 0) nxt[j] = i;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cin >> x;
        add(i, x);
    }

    for (int i = 1; i <= q; ++i) {
        cin >> l >> x;
        add(l, x);
        cout << ans << '\n';
    }

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

string add(string s) {
    int i = (int)s.size() - 1;
    while (s[i] == '1') {
        s[i] = '0';
        i--;
    }
    s[i] = '1';
    return s;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string l, r;
    cin >> l >> r;
    if (l == r) {
        cout << r << '\n';
        return 0;
    }
    if (l[0] != r[0]) {
        for (int i = 1; i <= n; ++i) cout << "1";
        return 0;
    }
    if (add(l) == r || r.back() == '1') {
        cout << r << '\n';
        return 0;
    }
    cout << add(r) << '\n';
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int const maxn = 1005;
int dp[maxn];
vector < vector < int > > T;

int ask(int lx1, int ly1, int rx1, int ry1, int lx2, int ly2, int rx2, int ry2) {
    cout << "? " << rx1 - lx1 + 1 << " " << ry1 - ly1 + 1 << " " << lx1 << " " << ly1
    << " " << lx2 << " " << ly2 << endl;
    int ans;
    cin >> ans;
    return ans;
}

int good(int l, int r) {
    if (l == r) return 1;

    int cnt = (r - l + 1) / 2;
    if (ask(T[l][0], T[l][1], T[l + cnt - 1][2], T[l + cnt - 1][3], T[l + cnt][0], T[l + cnt][1], T[l + 2 * cnt - 1][2], T[l + 2 * cnt - 1][3])) {
        return good(l + cnt, r);
    }
    return 0;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, cntn = 0, cntm = 0;
    cin >> n >> m;

    for (int i = n; i >= 1; --i) {
        if (n % i != 0 || dp[i] != 0) continue;

        for (int j = 2 * i; j <= n; j += i) {
            if (n % j == 0 && j % i == 0) {
                T = {};
                for (int k = 1; k <= j / i; ++k) {
                    T.push_back({(k - 1) * i + 1, 1, k * i, m});
                }
                if (good(0, (int)T.size() - 1)) dp[i] = 1;
                else dp[i] = 2;
                break;
            }
        }

        if (dp[i] == 2) {
            for (int j = 1; j <= n; ++j) {
                if (i % j == 0) dp[j] = 2;
            }
        }
        else {
            dp[i] = 1;
            for (int j = i; j <= n; ++j) {
                if (dp[j] == 1) {
                    int w = __gcd(i, j);
                    for (int pos = w; pos <= n; pos += w) {
                        dp[pos] = 1;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) cntn += (dp[i] == 1);
        dp[i] = 0;
    }

    for (int i = m; i >= 1; --i) {
        if (m % i != 0 || dp[i] != 0) continue;

        for (int j = 2 * i; j <= m; j += i) {
            if (m % j == 0 && j % i == 0) {
                T = {};
                for (int k = 1; k <= j / i; ++k) {
                    T.push_back({1, (k - 1) * i + 1, n, k * i});
                }
                if (good(0, (int)T.size() - 1)) dp[i] = 1;
                else dp[i] = 2;
                break;
            }
        }
        if (dp[i] == 2) {
            for (int j = 1; j <= i; ++j) {
                if (i % j == 0) {
                    dp[j] = 2;
                }
            }
        }
        else {
            dp[i] = 1;
            for (int j = i; j <= m; ++j) {
                if (dp[j] == 1) {
                    int w = __gcd(i, j);
                    for (int pos = w; pos <= m; pos += w) {
                        dp[pos] = 1;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= m; ++i) {
        if (m % i == 0) cntm += (dp[i] == 1);
    }
    cout << "! " << cntn * cntm << endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        cout << n / 2 + 1 << '\n';
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int const MAXN = 1e5 + 5;
int cnt[MAXN];

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, q, x, cnt2 = 0, cnt4 = 0;
    char type;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> x;
        
        cnt2 -= cnt[x] / 2;
        cnt4 -= cnt[x] / 4;
        cnt[x]++;
        cnt2 += cnt[x] / 2;
        cnt4 += cnt[x] / 4;
    }

    cin >> q;

    for (int i = 1; i <= q; ++i) {
        cin >> type >> x;
        cnt2 -= cnt[x] / 2;
        cnt4 -= cnt[x] / 4;
        
        if (type == '+') cnt[x]++;
        else cnt[x]--;
        
        cnt2 += cnt[x] / 2;
        cnt4 += cnt[x] / 4;
        
        if (cnt4 >= 1 && cnt2 >= 4) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100009;
int cnt[MAXN];
vector<int> a;
int n;

bool check(int x) {
    for (int i = 1; i <= n; i ++) cnt[i] = 0;
    for (int i = 0; i < n; i ++) cnt[a[i]]++;

    set<pair<int, int>, greater<pair<int, int>>> ss; //use greater comparator to sort set in descending order
    for (int i = 1; i <= n; i ++) {
        if (cnt[i] > 0) ss.insert({cnt[i], i});
    }

    vector<int> b;
    for (int i = 0; i < n; i ++) {
        if (i >= x && cnt[b[i - x]]) {
            ss.insert({cnt[b[i - x]], b[i - x]});
        }

        if (ss.empty()) return 0;
        b.push_back(ss.begin()->second);
        ss.erase(ss.begin());
        cnt[b.back()]--;
    }

    return 1;
}

signed main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);

	int ttt;
	cin >> ttt;

	while (ttt--) {
        cin >> n;

        a.resize(n);
        for (int i = 0; i < n; i ++) {
            cin >> a[i];
        }

        int l = 0, r = n;
        while (r - l > 1) {
            int m = (r + l) / 2;
            if (check(m)) {
                l = m;
            }

            else {
                r = m;
            }
        }

        cout << l - 1 << "\n";
	}

	return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
int const maxn = 2005;
char a[maxn][maxn];
int cnt_up[maxn][maxn], cnt_down[maxn][maxn], L[maxn], R[maxn];

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) cin >> a[i][j];
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i != 1 && a[i][j] == a[i - 1][j]) cnt_up[i][j] = cnt_up[i - 1][j] + 1;
            else cnt_up[i][j] = 0;
        }
    }
    for (int i = n; i >= 1; --i) {
        for (int j = 1; j <= m; ++j) {
            if (i != n && a[i][j] == a[i + 1][j]) cnt_down[i][j] = cnt_down[i + 1][j] + 1;
            else cnt_down[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int go = j;
            while (go <= m && a[i][j] == a[i][go]) go++;
            go--;
            for (int pos = j; pos <= go; ++pos) {
                if (pos == j) L[pos] = pos;
                else {
                    L[pos] = max(L[pos - 1], pos - min(cnt_up[i][pos], cnt_down[i][pos]));
                }
            }
            j = go;
        }
        for (int j = m; j >= 1; --j) {
            int go = j;
            while (go >= 1 && a[i][j] == a[i][go]) go--;
            go++;
            for (int pos = j; pos >= go; --pos) {
                if (pos == j) R[pos] = pos;
                else {
                    R[pos] = min(R[pos + 1], pos + min(cnt_up[i][pos], cnt_down[i][pos]));
                }
            }
            j = go;
        }
        for (int j = 1; j <= m; ++j) {
            ans += (ll)min(j - L[j] + 1, R[j] - j + 1);
        }
    }
    cout << ans << '\n';
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
int const maxn = 1e5 + 5, maxc = 1e6 + 5;
ll mod[2], P[2], p[2][maxc], rev_P[2];
vector < ll > h[2][maxn];
vector < int > sorted[maxn];
string s[maxn];
int nxt[maxc];
int a[maxc], dp[2][maxc], inf = 1e9 + 7;
int MOD = 1e9 + 7;

ll st(ll x, int y, int ok) {
    if (y == 0) return 1;
    if (y % 2 == 0) {
        ll d = st(x, y / 2, ok);
        return d * d % mod[ok];
    }
    return x * st(x, y - 1, ok) % mod[ok];
}

inline char get_c(int i, int x, int numb) {
    if (numb < x) return s[i][numb];
    if (numb + 1 < (int)s[i].size()) return s[i][numb + 1];
    return ' ';
}

inline ll get_hash(int t, int i, int x, int len) {
    if (len < x) return h[t][i][len];
    return (h[t][i][x] + (h[t][i][len + 1] - h[t][i][x + 1] + mod[t]) * rev_P[t]) % mod[t];
}

inline pair < ll, ll > get_h(int i, int x, int len) {
    return {get_hash(0, i, x, len), get_hash(1, i, x, len)};
}

inline int check(int i, int x, int j, int y) {
    int len1 = (int)s[i].size(), len2 = (int)s[j].size();
    if (x != len1) len1--;
    if (y != len2) len2--;
    int lef = 0, righ = min(len1, len2) + 1;
    while (righ - lef > 1) {
        int mid = (righ + lef) / 2;
        if (get_h(i, x, mid) == get_h(j, y, mid)) lef = mid;
        else righ = mid;
    }
    return get_c(i, x, lef) >= get_c(j, y, lef);
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    mod[0] = 1e9 + 7, mod[1] = 1e9 + 9, P[0] = 29, P[1] = 31, rev_P[0] = st(P[0], mod[0] - 2, 0), rev_P[1] = st(P[1], mod[1] - 2, 1);
    p[0][0] = 1, p[1][0] = 1;
    for (int i = 1; i < maxc; ++i) {
        for (int j = 0; j <= 1; ++j) p[j][i] = p[j][i - 1] * P[j] % mod[j];
    }
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        for (int j = 0; j <= 1; ++j) {
            h[j][i].push_back(0);
            for (int pos = 0; pos < (int)s[i].size(); ++pos) {
                h[j][i].push_back((h[j][i][pos] + p[j][pos] * (s[i][pos] - 'a' + 1)) % mod[j]);
            }
        }
        nxt[(int)s[i].size() - 1] = (int)s[i].size() - 1;
        for (int pos = (int)s[i].size() - 2; pos >= 0; --pos) {
            if (s[i][pos] != s[i][pos + 1]) nxt[pos] = pos + 1;
            else nxt[pos] = nxt[pos + 1];
        }
        int l = 0, r = (int)s[i].size() - 1;
        for (int j = 0; j < (int)s[i].size(); ++j) {
            if (s[i][nxt[j]] <= s[i][j]) a[l++] = j;
            else a[r--] = j;
        }
        for (int j = 0; j < (int)s[i].size(); ++j) {
            sorted[i].push_back(a[j]);
            if (a[j] == (int)s[i].size() - 1) sorted[i].push_back((int)s[i].size());
        }
    }
    for (int i = 0; i <= (int)s[1].size(); ++i) {
        dp[0][i] = 1;
    }
    for (int i = 2; i <= n; ++i) {
        int oks = (i - 1) % 2, ptr = 0, sum = 0, cur = -1;
        for (auto key : sorted[i]) {
            cur++;
            while (ptr < (int)sorted[i - 1].size() && check(i, key, i - 1, sorted[i - 1][ptr])) {
                sum += dp[(1^oks)][ptr];
                if (sum >= MOD) sum -= MOD;
                ptr++;
            }
            dp[oks][cur] = sum;
        }
    }
    int ans = 0;
    for (int i = 0; i <= (int)s[n].size(); ++i) {
        ans += dp[(n - 1) % 2][i];
        if (ans >= MOD) ans -= MOD;
    }
    cout << ans << '\n';
    return 0;
}