#include <iostream>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <array>
////#pragma GCC optimize(2)
//////#include <bits/stdc++.h>
////#define rep(i,from,to) for(int i=from;i<to;i++)
////#define ite2(x,y,arr) for(auto [x,y]:arr)
////#define pdd pair<double, double>
////#define ite(i,arr) for(auto &i:arr)
////#define MID(l,r) int mid=(l+r)>>1
////#define ALL(arr) arr.begin(),arr.end()
////#define AXY(a,x,y) int x=a.first,y=a.second
////#define vc vector
////#define vi vector<int>
////#define vll vector<long long>
////#define pii pair<int,int>
////typedef long long ll;
////typedef unsigned long long ull;
////using namespace std;
////
////
////#define FTY
////double inf = 521.1145314;
////
////namespace G {
////#ifdef FTY
////    const double eps = 1e-8;
////    const double PI = acos(-1);
////    struct Point {
////        double x, y;
////        Point() {
////            x = 0, y = 0;
////        }
////        Point(double x, double y) {
////            this->x = x;
////            this->y = y;
////        }
////    };
////    bool operator<(Point a, Point b) {
////        return a.x < b.x || a.x == b.x && a.y < b.y;
////    }
////    Point operator +(Point a, Point b) {
////        return Point(a.x + b.x, a.y + b.y);
////    }
////    Point operator -(Point a, Point b) {
////        return Point(a.x - b.x, a.y - b.y);
////    }
////    Point operator *(double a, Point b) {
////        return Point(a * b.x, a * b.y);
////    }
////    Point operator *(Point b, double a) {
////        return Point(a * b.x, a * b.y);
////    }
////    Point operator /(Point b, double a) {
////        return Point(b.x / a, b.y / a);
////    }
////    double len(Point a) {
////        return sqrt(a.x * a.x + a.y * a.y);
////    }
////    double dis(Point a, Point b) {
////        return len(a - b);
////    }
////    bool operator ==(Point a, Point b) {
////        return dis(a, b) <= eps||a.x==inf||b.x==inf;
////    }
////    bool operator !=(Point a, Point b) {
////        return !(a == b);
////    }
////    double operator *(Point a, Point b) {
////        return a.x * b.x + a.y * b.y;
////    }
////
////    double operator ^(Point a, Point b) {
////        return a.x * b.y - a.y * b.x;
////    }
////
////    double getAngel(double b, double a, double c) {
////        return acos((a * a + c * c - b * b) / (2 * a * c));
////    }
////    double getAngel(Point a, Point b) {
////        return acos(a * b / len(a) / len(b));
////    }
////    Point inter(Point p, Point v, Point q, Point w) {
////        if (fabs(v ^ w) <= eps) {
////            return { inf,inf };
////        }
////        Point u = p - q;
////        double t = (w ^ u) / (v ^ w);
////        return p + t * v;
////    }
////
////
////#endif
////}
////using namespace G;
////#define int ll
////const int mod = (int)1e9 + 7;
//////template <class T>
//////T __gcd(T a, T b) {
//////    if (a < b) swap(a, b);
//////    return b ? __gcd(b, a % b) : a;
//////}
////template <class T>
////T __lcm(T a, T b) {
////    T num = __gcd(a, b);
////    return a / num * b;
////}
////inline int lowbit(int num) { return num & (-num); }
////inline int qmi(int a, int b) {
////    a %= mod;
////    ll res = 1;
////    while (b) {
////        if (b & 1) res = (ll)res * a % mod;
////        a = (ll)a * a % mod;
////        b >>= 1;
////    }
////    return res;
////}
////int inv(int num) {
////    return qmi(num, mod - 2);
////}
////void solve() {
////    int n, m; cin >> n >> m;
////    vector<bitset<1024>>f(1024);
////    f[0][0] = 1;
////    auto g = f;
////    vector<int>v(n + 1), w(n + 1);
////    for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];
////    for (int i = 1; i <= n; i++) {
////        for (int j = 0; j < 1024; j++) {
////            g[j] |= (f[j ^ w[i]] << v[i]);
////        }
////        for (int j = 0; j <1024; j++) {
////            f[j] |= g[j];
////        }
////    }
////    for (int i = 1023; i >= 1; i--) {
////        if (f[i][m]) {
////            cout << i << "\n";
////            return;
////        }
////    }
////    cout << 1 << "\n";
////}
////signed main() {
////    ios::sync_with_stdio(false);
////    cin.tie(0);
////    int tc = 1;
////    cin >> tc;
////    for (int i = 1; i <= tc; i++) {
////        solve();
////    }
////}

using namespace std;
#define int long long
#define endl '\n'
#define eb emplace_back
#define INF (int)(1e18)
const int MOD = 1e9 + 7;
int fast(int x, int n) {
	int ret = 1;
	while (n) {
		if (n & 1) ret = ret * x % MOD;
		x = x * x % MOD;
		n >>= 1;
	}
	return ret;
}

void run() {
	int n, m;
	cin >> n >> m;
	vector<int> w(n + 1, 0), v(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i];
	}
	vector<vector<bitset<1024> > > dp(2, vector<bitset<1024> >(1024));
	int now = 0;
	dp[now][0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 1024; j++) {
			dp[now ^ 1][j ^ v[i]] |= (dp[now][j] << w[i]);
			dp[now ^ 1][j] |= dp[now][j];
		}
		now ^= 1;
	}
	for (int i = 1023; i >= 0; i--) {
		if (dp[now][i][m] == 1) return (void)(cout << i << endl);
	}
	cout << 1 << endl;






	return;
}
signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T = 1;
	cin >> T;
	while (T--) {
		run();
	}

	return 0;
}