C++ :

#include <cstdio>
typedef long long ll;
/* Sn 长度 = 2^n - 1；位置 k(1-based)
   若 k == mid -> '1'；若 k < mid -> 递归 Sn-1 的 k；否则 -> invert(Sn-1 的 mid2 - k) */
int main(){
    int T; if(scanf("%d", &T) != 1) return 0;
    while(T--){
        int n; ll k;
        scanf("%d %lld", &n, &k);
        int level = n, flip = 0;
        while(level > 1){
            ll len = (1LL << level) - 1;
            ll mid = (len + 1) / 2;
            if(k == mid) break;
            if(k > mid){
                k = len - k + 1;
                flip ^= 1;
            }
            level--;
        }
        int bit;
        if(level == 1){ bit = 0; }
        else { bit = 1; }
        printf("%d\n", bit ^ flip);
    }
    return 0;
}