#include "message.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define All(x)   x.begin(), x.end()
#define debug(x) cout << #x << " = " << x << "\n"

template<typename T> bool chmax(T &u, T v) { if (u < v) { u = v; return true; } return false; }

template<typename T>
ostream& operator<<(ostream& os, const vector<T> &v) {
    os << "["; bool _first = true;
    for (auto i : v) { if (!_first) { os << ", "; } os << i; _first = false; }
    return os << "]";
}

const ll INF = 1'000'000'000'000'000'000;

const int PKT_SIZE  = 31;
const int FREE_IDX  = 16;
const int CLEO_IDX  = 15;
const int M_SZ_BITS = 10;
const int F_ID_BITS = 5;

void send_message(vector<bool> M, vector<bool> C) {
    int S = M.size();
    vector<int> free_indices;
    for (int i = 0; i < PKT_SIZE; i++) if (!C[i]) free_indices.push_back(i);

    vector<int> f_id_transmit;
    for (auto f : free_indices) {
        for (int i = 0; i < F_ID_BITS; i++) {
            f_id_transmit.push_back((f >> i) & 1);
        }
    }

    // Transmit free indices
    int transmitted_free = 0;
    int ptr = 0;
    while (ptr < (int)f_id_transmit.size()) {
        vector<bool> cur(PKT_SIZE);
        if (FREE_IDX - transmitted_free > CLEO_IDX) {
            // transmit through unknown bits
            for (int i = transmitted_free; i < FREE_IDX; i++) {
                // cerr << f_id_transmit[ptr];
                cur[free_indices[i]] = f_id_transmit[ptr];
            }
            ptr++;
        }

        // transmit through known bits
        for (int i = 0; i < transmitted_free; i++) {
            if (ptr < (int)f_id_transmit.size()) {
                // cerr << f_id_transmit[ptr];
                cur[free_indices[i]] = f_id_transmit[ptr++];
            }
        }
        // cerr << "\n";

        send_packet(cur);
        transmitted_free = ptr / 5;
    }
    
    vector<bool> T;
    for (int i = 0; i < M_SZ_BITS; i++) T.push_back((S-1) & (1 << i));
    for (auto i : M) T.push_back(i);

    ptr = 0;
    while (ptr < (int)T.size()) {
        vector<bool> cur(PKT_SIZE);
        for (auto idx : free_indices) if (ptr < (int)T.size()) {
            cur[idx] = T[ptr++];
        }
        send_packet(cur);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    int read_packets = 0;

    vector<int> free_indices;
    vector<bool> is_free(PKT_SIZE);
    queue<bool> pending;
    while ((int)free_indices.size() < FREE_IDX) {
        // cerr << free_indices << "\n";

        vector<bool> cur_packet = R[read_packets++];

        if (FREE_IDX - (int)free_indices.size() > CLEO_IDX) {
            // read unknown bits
            int cnt[2] = {};
            for (int j = 0; j < PKT_SIZE; j++) if (!is_free[j]) {
                cnt[cur_packet[j]]++;
            }
            pending.push((cnt[0] > cnt[1]) ? 0 : 1);
        }

        // read known bits
        for (auto f : free_indices) pending.push(cur_packet[f]);

        while (pending.size() >= 5 && (int)free_indices.size() < FREE_IDX) {
            int c = 0;
            for (int i = 0; i < 5; i++) {
                c |= (pending.front() << i);
                pending.pop();
            }
            free_indices.push_back(c);
            is_free[c] = true;
        }
    }

    vector<bool> transmitted;
    while (read_packets < (int)R.size()) {
        vector<bool> cur_packet = R[read_packets++];
        for (auto j : free_indices) transmitted.push_back(cur_packet[j]);
    }

    int sz = 0;
    for (int i = 0; i < M_SZ_BITS; i++) if (transmitted[i]) {
        sz |= (1 << i);
    }
    sz++;

    vector<bool> ans;
    for (int i = M_SZ_BITS; i < M_SZ_BITS + sz; i++) ans.push_back(transmitted[i]);

    return ans;
}

#ifdef Zanite

namespace {
const int PACKET_SIZE = 31;
const int CALLS_CNT_LIMIT = 100;

int calls_cnt;
vector<bool> C(PACKET_SIZE);
vector<vector<bool>> R;

void quit(const char* message) {
    printf("%s\n", message);
    exit(0);
}

void run_scenario() {
    R.clear();
    calls_cnt = 0;

    int S;
    assert(1 == scanf("%d", &S));
    vector<bool> M(S);
    for (int i = 0; i < S; i++) {
        int bit;
        assert(1 == scanf("%d", &bit));
        assert((bit == 0) || (bit == 1));
        M[i] = bit;
    }

    for (int i = 0; i < PACKET_SIZE; i++) {
        int bit;
        assert(1 == scanf("%d", &bit));
        assert((bit == 0) || (bit == 1));
        C[i] = bit;
    }

    send_message(M, C);
    vector<bool> D = receive_message(R);

    int K = (int)R.size();
    int L = (int)D.size();
    printf("%d %d\n", K, L);
    for (int i = 0; i < L; i++)
        printf("%s%d", (i == 0 ? "" : " "), (D[i] ? 1 : 0));
    printf("\n");
}

vector<bool> taint(const vector<bool>& A) {
    vector<bool> B = A;
    bool bit = 0;
    for (int i = 0; i < PACKET_SIZE; i++)
        if (C[i] == 1) {
            B[i] = bit;
            bit = !bit;
        }
    return B;
}

} // namespace

vector<bool> send_packet(vector<bool> A) {
    calls_cnt++;
    if (calls_cnt > CALLS_CNT_LIMIT)
        quit("Too many calls");
    if ((int)A.size() != PACKET_SIZE)
        quit("Invalid argument");

    vector<bool> B = taint(A);
    R.push_back(B);
    return B;
}

int main() {
    int T;
    assert(1 == scanf("%d", &T));
    for (int i = 1; i <= T; i++)
        run_scenario();
}

#endif