#include <bits/stdc++.h>

#define OobugoO_IOS std::ios::sync_with_stdio(false), std::cin.tie(nullptr)

typedef long long ll;

void solve() {
    int n;
    std::cin >> n;
    int num = 0;
    int p;
    for (int i = 1; i < n; i += 2) {
        std::cout << "? " << i << " " << i + 1 << "\n";
        int f;
        std::cin >> f;
        if (f) {
            num ++;
            p = i;
        }
    }
    if ((n & 1) && num == 0) {
        int f1, f2, f3;
        std::cout << "? " << n << " " << 1 << "\n";
        std::cin >> f1;
        std::cout << "? " << n << " " << 2 << "\n";
        std::cin >> f2;
        std::cout << "? " << n << " " << 3 << "\n";
        std::cin >> f3;
        if (f1 && f2 && f3) {
            std::cout << "! " << 1 << "\n";
        } else {
            std::cout << "! " << 0 << "\n";
        }
    } else if (num == 0 || num >= 2) {
        std::cout << "! " << 1 << "\n";
    } else {
        int f1;
        std::cout << "? " << p << " " << ((p + 1) % n) + 1 << "\n";
        std::cin >> f1;
        if (f1) {
            int f2;
            std::cout << "? " << p << " " << ((p + 2) % n) + 1 << "\n";
            std::cin >> f2;
            if (f2) {
                std::cout << "! " << 1 << "\n";
            } else {
                std::cout << "! " << 0 << "\n";
            }
        } else {
            int f2, f3;
            std::cout << "? " << p + 1 << " " << ((p + 1) % n) + 1 << "\n";
            std::cin >> f2;
            std::cout << "? " << p + 1 << " " << ((p + 2) % n) + 1 << "\n";
            std::cin >> f3;
            if (f2 && f3) {
                std::cout << "! " << 1 << "\n";
            } else {
                std::cout << "! " << 0 << "\n";
            }
        }
    }
}
int main() {

#ifdef Onlion_Judge
    freopen("IO/input.in", "r", stdin);
    freopen("IO/output.out", "w", stdout);
#endif

    // OobugoO_IOS;
    int t = 1;
    std::cin >> t;
    while(t--) {
        solve();
    }
}