#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
bitset<1025>F[2][1025];
int n,m,T;
int main(){
	T=read();
	while(T--){
		n=read(),m=read();
		for(int i=0;i<1024;i++)
			F[0][i].reset(),F[1][i].reset();
		F[0][0][0]=1;
		for(int i=1;i<=n;i++){
			int o=(i&1),u=read(),v=read();
			for(int j=0;j<1024;j++)
				F[o][j]=F[o^1][j]|(F[o^1][j^v]<<u);
		}int flg=0;
		for(int i=1023;i>=0;--i)
			if(F[n&1][i][m]){printf("%d\n",i);flg=1;break;}
		if(!flg)puts("1");
	}
	return 0;
}