#include<bits/stdc++.h>
typedef long long i64;
typedef unsigned long long u64;
unsigned long long s[2];
unsigned long long xorshift128plus() {
	unsigned long long x = s[0];
	const unsigned long long y = s[1];
	x ^= x << 23;
	s[1] = x ^ y ^ (x >> 17) ^ (y >> 26);
	return s[0] = y;
}

const int MX = 1111;

int n, Cmax, Hmax;
int C[MX][MX];
int H[MX][MX],Hx[MX][MX];
struct edge{
	int to;
	i64 v;
	bool operator<(const edge&e)const{return v<e.v;}
}e[MX];
struct edge3{
	int a,b;
	i64 v;
	bool operator<(const edge3&e)const{return v<e.v;}
}e3[MX*MX];
int f[MX];
int gf(int x){
	while(x!=f[x])x=f[x]=f[f[x]];
	return x;
}
i64 tot_cost=0;
void mins(int&a,int b){if(a>b)a=b;}
struct Ans{
	bool s[MX][MX];
	i64 cost;
	int deg[MX];
	void ae(int a,int b){
		s[a][b]=s[b][a]=1;
		cost+=H[a][++deg[a]]+H[b][++deg[b]]+C[a][b];
	}
	void de(int a,int b){
		s[a][b]=s[b][a]=0;
		cost-=H[a][deg[a]--]+H[b][deg[b]--]+C[a][b];
	}
	void gx(int c){
		for(int i=0;i<n;++i){
			for(int j=0;j<n;++j){
				int s=0;
				Hx[i][j]=INT_MAX;
				for(int k=0;k<c&&j+k<n;++k){
					s+=H[i][j+k];
					mins(Hx[i][j],s);
				}
			}
		}
	}
	void init(){
		memset(this,0,sizeof(Ans));
		cost=0;
		for(int i=0;i<MX;++i)cost+=H[i][0];
	}
	void calc(){
		init();
		gx(2);
		int id[MX];
		for(int i=0;i<n;++i)id[i]=i;
		for(int i=1;i<n;++i){
			int x=id[i];
			for(int j=0;j<i;++j){
				int u=id[j];
				e[j]=(edge){u,C[x][u]+Hx[u][deg[u]+1]};
			}
			std::sort(e,e+i);
			for(int j=1;j<i;++j)e[j].v+=e[j-1].v;
			i64 s=H[x][0];
			int w=0;
			for(int j=0;j<i;++j){
				e[j].v+=s+Hx[x][j+1];
				s+=H[x][j+1];
				if(e[j]<e[w])w=j;
			}
			for(int j=0;j<=w;++j)ae(x,e[j].to);
		}
	}
	void cal2(int pX){
		init();
		int deg[MX];
		for(int i=0;i<n;++i){
			int s=H[i][0],mw=1,mv=INT_MAX;
			for(int j=1;j<pX;++j){
				s+=H[i][j];
				if(s<mv)mv=s,mw=j;
			}
			deg[i]=mw;
			f[i]=i;
		}
		int ep=0;
		for(int i=0;i<n;++i){
			for(int j=0;j<i;++j){
				e3[ep++]=(edge3){i,j,C[i][j]};
			}
		}
		std::sort(e3,e3+ep);
		for(int i=0;i<ep;++i){
			int a=e3[i].a,b=e3[i].b;
			int x=gf(a),y=gf(b);
			if(!s[a][b]&&deg[a]>0&&deg[b]>0){
				ae(a,b);
				f[x]=y;
				--deg[a],--deg[b];
			}
		}
		for(int i=0;i<ep;++i){
			int a=e3[i].a,b=e3[i].b;
			int x=gf(a),y=gf(b);
			if(!s[a][b]&&x!=y){
				ae(a,b);
				f[x]=y;
			}
		}
//		gx(2);
//		for(int i=1;i<n;++i){
//			int mw=0,mv=0x7fffffff;
//			for(int j=0;j<i;++j){
//				int v=C[i][j]+Hx[j][deg[j]+1];
//				if(v<mv)mv=v,mw=j;
//			}
//			ae(i,mw);
//		}
	}
	void pr(){
		#ifdef LOC
		tot_cost+=cost;
		printf("%g\n",double(cost));
		#else
		for(int i=0;i<n;++i){
			for(int j=0;j<n;++j)putchar(s[i][j]+'0');
			putchar(10);
		}
		#endif
	}
}a1,a2;
#ifdef LOC
std::mt19937 mt(111);
u64 gr(){
	u64 x=0;
	for(int i=0;i<10;++i)x=x<<7^mt();
	return x%u64(1e18);
}
#endif
int main() {
	int T;
	#ifdef LOC
	T=5;
	#else
	scanf("%d", &T);
	#endif
	for (int t = 0; t < T; t++) {
		#ifdef LOC
		n=1000;
		int cv[]={40000,100000,200000,500000,1000000};
		Cmax=cv[t];
		Hmax=1000000;
		#else
		scanf("%d %d %d", &n, &Cmax, &Hmax);
		#endif
		for (int i = 0; i < n; i++) {
			C[i][i] = 0;
			#ifdef LOC
			s[0]=gr();s[1]=gr();
			#else
			scanf("%llu %llu", &s[0], &s[1]);
			#endif
			for (int j = i + 1; j < n; j++) {
				C[i][j] = C[j][i] = xorshift128plus() % (Cmax + 1);
			}
		}
		for(int i=0;i<n;i++){
			#ifdef LOC
			s[0]=gr();s[1]=gr();
			#else
			scanf("%llu %llu", &s[0], &s[1]);
			#endif
			for(int j=0;j<n;j++){
				H[i][j] = xorshift128plus() % (Hmax + 1);
			}
			for(int j=n;j;--j)H[i][j]-=H[i][j-1];
		}
		int L,R;
		if(Cmax==40000)L=40,R=50;
		else if(Cmax==100000)L=28,R=38;
		else if(Cmax==200000)L=22,R=32;
		else if(Cmax==500000)L=14,R=24;
		else L=10,R=20;
		for(int i=L;i<=R;++i){
			a2.cal2(i);
			if(i==L||a2.cost<a1.cost)a1=a2;
		}
		a1.pr();
		fprintf(stderr, "%lld\n", a1.cost);
	}
	#ifdef LOC
	printf("tot=%g\n",double(tot_cost));
	printf("cc:%g\n",double(2965779435)/2);
	#endif
	return 0;
}