#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    map<pair<int,int>,int>hm;
    hm[{2,2}] = 2;
    hm[{2,3}] = 3;
    hm[{2,4}] = 5;
    hm[{4,4}] = 8;
    hm[{2,5}] = 6;
    hm[{4,5}] = 9;
    hm[{2,6}] = 10;
    hm[{4,6}] = 17;
    hm[{6,6}] = 30;
    hm[{2,7}] = 10;
    hm[{4,7}] = 33;
    hm[{6,7}] = 32;
    hm[{2,8}] = 18;
    hm[{4,8}] = 65;
    hm[{6,8}] = 64;
    hm[{8,8}] = 127;
    hm[{2,9}] = 18;
    hm[{4,9}] = 66;
    hm[{6,9}] = 127;
    hm[{8,9}] = 128;
    hm[{2,10}] = 34;
    hm[{4,10}] = 130;
    hm[{6,10}] = 255;
    hm[{8,10}] = 256;
    hm[{10,10}] = 508;
    hm[{2,11}] = 34;
    hm[{4,11}] = 258;
    hm[{6,11}] = 511;
    hm[{8,11}] = 512;
    hm[{10,11}] = 511;
    hm[{2,12}] = 66;
    hm[{4,12}] = 514;
    hm[{6,12}] = 1023;
    hm[{8,12}] = 1024;
    hm[{10,12}] = 1023;
    hm[{12,12}] = 2046;
    hm[{2,13}] = 66;
    hm[{4,13}] = 514;
    hm[{6,13}] = 1025;
    hm[{8,13}] = 2047;
    hm[{10,13}] = 2046;
    hm[{12,13}] = 2048;
    hm[{2,14}] = 130;
    hm[{4,14}] = 1026;
    hm[{6,14}] = 2049;
    hm[{8,14}] = 4095;
    hm[{10,14}] = 4094;
    hm[{12,14}] = 4096;
    hm[{14,14}] = 8186;
    hm[{2,15}] = 130;
    hm[{4,15}] = 2050;
    hm[{6,15}] = 4097;
    hm[{8,15}] = 8191;
    hm[{10,15}] = 8190;
    hm[{12,15}] = 8192;
    hm[{14,15}] = 8190;
    hm[{2,16}] = 258;
    hm[{4,16}] = 4098;
    hm[{6,16}] = 8192;
    hm[{8,16}] = 16383;
    hm[{10,16}] = 16382;
    hm[{12,16}] = 16383;
    hm[{14,16}] = 16382;
    hm[{16,16}] = 32767;
    hm[{2,17}] = 258;
    hm[{4,17}] = 4098;
    hm[{6,17}] = 16383;
    hm[{8,17}] = 16384;
    hm[{10,17}] = 32765;
    hm[{12,17}] = 32766;
    hm[{14,17}] = 32765;
    hm[{16,17}] = 32767;
    hm[{2,18}] = 514;
    hm[{4,18}] = 8194;
    hm[{6,18}] = 32767;
    hm[{8,18}] = 32768;
    hm[{10,18}] = 65533;
    hm[{12,18}] = 65534;
    hm[{14,18}] = 65533;
    hm[{16,18}] = 65535;
    hm[{18,18}] = 131064;
    hm[{2,19}] = 514;
    hm[{4,19}] = 16386;
    hm[{6,19}] = 32768;
    hm[{8,19}] = 65536;
    hm[{10,19}] = 131069;
    hm[{12,19}] = 131070;
    hm[{14,19}] = 131069;
    hm[{16,19}] = 131071;
    hm[{18,19}] = 131069;
    hm[{2,20}] = 1026;
    hm[{4,20}] = 32770;
    hm[{6,20}] = 65536;
    hm[{8,20}] = 131072;
    hm[{10,20}] = 262141;
    hm[{12,20}] = 262142;
    hm[{14,20}] = 262141;
    hm[{16,20}] = 262143;
    hm[{18,20}] = 262141;
    hm[{20,20}] = 524284;
    hm[{2,21}] = 1026;
    hm[{4,21}] = 32770;
    hm[{6,21}] = 131072;
    hm[{8,21}] = 262144;
    hm[{10,21}] = 262144;
    hm[{12,21}] = 524286;
    hm[{14,21}] = 524284;
    hm[{16,21}] = 524287;
    hm[{18,21}] = 524284;
    hm[{20,21}] = 524287;
    hm[{2,22}] = 2050;
    hm[{4,22}] = 65538;
    hm[{6,22}] = 262144;
    hm[{8,22}] = 524288;
    hm[{10,22}] = 524288;
    hm[{12,22}] = 1048574;
    hm[{14,22}] = 1048572;
    hm[{16,22}] = 1048575;
    hm[{18,22}] = 1048572;
    hm[{20,22}] = 1048575;
    hm[{22,22}] = 2097142;
    hm[{2,23}] = 2050;
    hm[{4,23}] = 131074;
    hm[{6,23}] = 524288;
    hm[{8,23}] = 1048576;
    hm[{10,23}] = 1048576;
    hm[{12,23}] = 2097150;
    hm[{14,23}] = 2097148;
    hm[{16,23}] = 2097151;
    hm[{18,23}] = 2097148;
    hm[{20,23}] = 2097151;
    hm[{22,23}] = 2097148;
    hm[{2,24}] = 4098;
    hm[{4,24}] = 262146;
    hm[{6,24}] = 1048576;
    hm[{8,24}] = 2097152;
    hm[{10,24}] = 2097151;
    hm[{12,24}] = 4194302;
    hm[{14,24}] = 4194300;
    hm[{16,24}] = 4194303;
    hm[{18,24}] = 4194300;
    hm[{20,24}] = 4194302;
    hm[{22,24}] = 4194300;
    hm[{24,24}] = 8388605;
    hm[{2,25}] = 4098;
    hm[{4,25}] = 262146;
    hm[{6,25}] = 1048577;
    hm[{8,25}] = 2097153;
    hm[{10,25}] = 4194302;
    hm[{12,25}] = 4194304;
    hm[{14,25}] = 8388603;
    hm[{16,25}] = 8388607;
    hm[{18,25}] = 8388603;
    hm[{20,25}] = 8388605;
    hm[{22,25}] = 8388603;
    hm[{24,25}] = 8388606;
    hm[{2,26}] = 8194;
    hm[{4,26}] = 524290;
    hm[{6,26}] = 2097153;
    hm[{8,26}] = 4194305;
    hm[{10,26}] = 8388606;
    hm[{12,26}] = 8388608;
    hm[{14,26}] = 16777211;
    hm[{16,26}] = 16777215;
    hm[{18,26}] = 16777211;
    hm[{20,26}] = 16777213;
    hm[{22,26}] = 16777211;
    hm[{24,26}] = 16777214;
    hm[{26,26}] = 33554420;
    hm[{2,27}] = 8194;
    hm[{4,27}] = 1048578;
    hm[{6,27}] = 4194305;
    hm[{8,27}] = 8388609;
    hm[{10,27}] = 16777214;
    hm[{12,27}] = 16777216;
    hm[{14,27}] = 33554427;
    hm[{16,27}] = 33554431;
    hm[{18,27}] = 33554427;
    hm[{20,27}] = 33554429;
    hm[{22,27}] = 33554427;
    hm[{24,27}] = 33554430;
    hm[{26,27}] = 33554427;
    hm[{2,28}] = 16386;
    hm[{4,28}] = 2097154;
    hm[{6,28}] = 8388609;
    hm[{8,28}] = 16777217;
    hm[{10,28}] = 33554430;
    hm[{12,28}] = 33554432;
    hm[{14,28}] = 67108859;
    hm[{16,28}] = 67108863;
    hm[{18,28}] = 67108859;
    hm[{20,28}] = 67108861;
    hm[{22,28}] = 67108859;
    hm[{24,28}] = 67108862;
    hm[{26,28}] = 67108859;
    hm[{28,28}] = 134217722;
    hm[{2,29}] = 16386;
    hm[{4,29}] = 2097154;
    hm[{6,29}] = 16777217;
    hm[{8,29}] = 33554433;
    hm[{10,29}] = 67108862;
    hm[{12,29}] = 67108864;
    hm[{14,29}] = 67108863;
    hm[{16,29}] = 134217727;
    hm[{18,29}] = 134217722;
    hm[{20,29}] = 134217725;
    hm[{22,29}] = 134217722;
    hm[{24,29}] = 134217726;
    hm[{26,29}] = 134217722;
    hm[{28,29}] = 134217726;
    hm[{2,30}] = 32770;
    hm[{4,30}] = 4194306;
    hm[{6,30}] = 33554433;
    hm[{8,30}] = 67108865;
    hm[{10,30}] = 134217726;
    hm[{12,30}] = 134217728;
    hm[{14,30}] = 134217727;
    hm[{16,30}] = 268435455;
    hm[{18,30}] = 268435450;
    hm[{20,30}] = 268435453;
    hm[{22,30}] = 268435450;
    hm[{24,30}] = 268435454;
    hm[{26,30}] = 268435450;
    hm[{28,30}] = 268435454;
    hm[{30,30}] = 536870898;
    while(t--){
        int a,p;
        cin >> a >> p;
        if(hm.count({a,p})){
            cout << hm[{a,p}] << '\n';
            continue;
        }
        if(a%2==1){
            cout << "1\n";
            continue;
        }
        int v = 1<<((p+1)/2);
        if(a%v == 0){
            cout << (1<<(p-1)) << '\n';
            continue;
        }
        if(a%8 == 0){
            cout << (1<<(p-1))-1 << '\n';
            continue;
        }
        if(a%4 == 0){
            cout << (1<<(p-1))-2 << '\n';
            continue;
        }
        if(a%2 == 0){
            cout << (1<<(p-1))-4 << '\n';
            continue;
        }


    }
    return 0;
}