#include <iostream>
#include <math.h>
using namespace std;

unsigned int F[1000000];
int z;
int s[1000001];
int p[1000001];

void fib()
{
    F[0] = 1;
    F[1] = 1;

    for(int i = 2; i < 10; ++i){
        F[i] = F[i-1] + F[i-2];
    }
}


int main()
{
    cout << 3 % 2 << endl;
    ios_base::sync_with_stdio(false);
    fib();
    cin >> z;
    for(int i = 0; i < z; ++i)
        cin >> s[i] >> p[i];


    for(int i = 0; i < z; i++) {
        //int h = F[s[i]];
        //h >> p[i];
        cout << "F[s[i]] = " << F[s[i]] << " % " << pow(2, p[i]) << endl;
        //F[s[i]]<< p[i];
        int k = pow(2, s[i]);
        int j = F[s[i]];
        cout << j % k << endl;
    }



    return 0;
}