bool is_odd_graph[20000][20000];
int main() {
    is_odd_graph[1][1] = 1;
    for(int i = 1; i < 20000; ++i) {
        for (int j = 1; j <= i-1; ++j) {
            if (!is_odd_graph[i-1][j]) continue;

            int previous_reduced = j;
            int new_weight = 1;
            while (true) {
                // Przypadek 1: w previous_reduced nie było new_weight lub zlepiamy je w jeden
                is_odd_graph[i][previous_reduced|new_weight] ^= 1;
                if (!(previous_reduced&new_weight)) break;
                // Przypadek 2: wyciągamy new_weight z previous_reduced i zlepiamy z naszym w podwójny
                previous_reduced -= new_weight;
                new_weight <<= 1;
            }
        }
    }

    int Q;
    scanf("%d", &Q);
    REP(q,Q) {
        int N, K;
        scanf("%d%d", &N, &K);

        K = N-K;
        bool res = is_odd_graph[N][K];
        for (int lb = 1; !(lb&K); lb <<= 1) res ^= is_odd_graph[N][K + lb];
        printf("%d\n", res);
    }
}