#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
#define  pii pair<int, int> 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
} 
template <typename T> void inline pr(T x) {
    if (x < 0) { putchar('-'); pr(-x); return ; }
    if (x >= 10) pr(x / 10);
    putchar((x % 10) + '0');
}

const int N = 2e3 + 10, M = N * 2, mod = 1e9 + 7;
inline LL ksm(LL a, LL b){
    LL ans = 1; 
    for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
//----------------------------------------------------------------------------------------//
int f[1100], tr[2100][1100 * 2][2];
int tot;
int idx[N];
void insert(int u, int w) {
    int p = 0;
    for(int i = 9; i >= 0; i--) {
        int c = w >> i & 1;
        if(!tr[u][p][c]) tr[u][p][c] = ++idx[u];
        p = tr[u][p][c];
    }//10位 
}
int ask(int u, int w) {
    int p = 0;
    int res = 0;
    for(int j = 9; j >= 0; j--) {
        int c = w >> j & 1;
        if(tr[u][p][!c]) {
            res += 1 << j, p = tr[u][p][!c];
        } else {
            p = tr[u][p][c];
        }
    }
    return res;
}
void solve() {
    memset(f, -1, sizeof f);
    memset(tr, 0, sizeof tr);
    memset(idx, 0, sizeof idx);
    f[0] = 0;//记录的是体积 
    tot = 0;
    int n, m;
    read(n), read(m);
    insert(0, 0);
    for(int i = 1; i <= n; i++) {
        int v, w;
        read(v), read(w);
        for(int j = m; j >= v; j--) {
            if(f[j - v] == -1) continue;//表示的是体积位j 
            int val = ask(j - v, w);
            f[j] = max(f[j], val);
            insert(j, val);
        }
    }
    cout << f[m] << '\n';
}
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
    // auto now = clock();
#endif
    int T;
    read(T);
    while(T--) {
        solve();
    }    

// #ifdef JANGYI

//     cout << "================================" << endl;
//     cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
// #endif
    return 0;
}