#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 10
#define M 1000000
#define K 6
using namespace std;
const long long inf=(long long)(1e12);
const long long INF=(long long)(1e18);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int T,n,len,ds[M+1],tong[N+1],length,sz[M+1],pw10[K+1],d[N+1],dp[M+1][K+1],dp2[M+1][K+1];
long long F[1<<N][1<<N],ans;
int calc(int len,int l,int r,int x)
{
	if (l==0&&r==pw10[len]-1) return dp2[x][len];
	if (l/pw10[len-1]==r/pw10[len-1]) return calc(len-1,l%pw10[len-1],r%pw10[len-1],x)&(((1<<10)-1)^(1<<(l/pw10[len-1])));
	else
	{
		int sl=l/pw10[len-1],sr=r/pw10[len-1],res=0;
		for (int i=sl;i<=sr;++i)
		{
			if (i==sl) res|=(calc(len-1,l-i*pw10[len-1],pw10[len-1]-1,x)&(((1<<10)-1)^(1<<i))),x+=((i+1)*pw10[len-1]-l);
			else if (i==sr) res|=(calc(len-1,0,r-i*pw10[len-1],x)&(((1<<10)-1)^(1<<i))),x+=(r-i*pw10[len-1]+1);
			else res|=(calc(len-1,0,pw10[len-1]-1,x)&(((1<<10)-1)^(1<<i))),x+=pw10[len-1];
		}
		return res;
	}
}
bool query(int l,int r)
{
	if (sz[l]==sz[r]) return !calc(sz[l],l,r,0);
	else
	{
		int x=0;
		bool op=1;
		for (int i=sz[l];i<=sz[r];++i)
		{
			if (i==sz[l]) op&=(!calc(i,l,pw10[i]-1,x)),x+=pw10[i]-l;
			else if (i==sz[r]) op&=(!calc(i,pw10[i-1],r,x)),x+=r-pw10[i-1]+1;
			else op&=(!calc(i,pw10[i-1],pw10[i]-1,x)),x+=pw10[i]-pw10[i-1];
		}
		return op;
	}
}
int main()
{
	char c;
	int d;
	long long res;
	for (int i=1;i<=M;++i) sz[i]=sz[i/10]+1;
	pw10[0]=1;
	for (int i=1;i<=6;++i) pw10[i]=pw10[i-1]*10;
	for (int i=0;i<(1<<10);++i)
		for (int j=0;j<(1<<10);++j)
			F[i][j]=inf;
	for (int i=1;i<(1<<10);++i)
		if (i!=1)
		{
			length=0;
			for (int j=0;j<=9;++j)
				if ((i>>j)&1)
					tong[++length]=j;
			sort(tong+1,tong+length+1);
			if (!tong[1]) swap(tong[1],tong[2]);
			res=0;
			for (int j=1;j<=length;++j) res=res*10+tong[j];
			F[i][i]=min(F[i][i],res);
			for (int j=0;j<=8;++j) F[i|((i||j)?(1<<j):0)][i|(1<<(j+1))]=min(F[i|((i||j)?(1<<j):0)][i|(1<<(j+1))],res*10+j);
			for (int j=0;j<=8;++j) F[i|((i||j)?(1<<j):0)|(1<<9)][i|(1<<(j+1))|(1<<0)]=min(F[i|((i||j)?(1<<j):0)|(1<<9)][i|(1<<(j+1))|(1<<0)],res*100+j*10+9);
		}
	for (int i=(1<<10)-1;i>=0;--i)
		for (int j=(1<<10)-1;j>=0;--j)
			for (int k=0;k<=9;++k)
			{
				if (!((i>>k)&1)) F[i][j]=min(F[i][j],F[i|(1<<k)][j]);
				if (!((j>>k)&1)) F[i][j]=min(F[i][j],F[i][j|(1<<k)]);
			}
	T=read();
	while (T--)
	{
		n=read(),ans=INF,len=sz[n-1];
		for (int i=0;i<n;++i) cin>>c,ds[i]=c-'0';
		for (int i=0;i<n;++i) dp[i][0]=dp2[i][0]=1<<ds[i];
		for (int i=0;i<n;++i)
			for (int j=1;j<=len;++j)
			{
				dp[i][j]=0;
				for (int k=9;k>=0;--k)
					if (i>=(9-k)*pw10[j-1])
						dp[i][j]|=dp[i-(9-k)*pw10[j-1]][j-1]&(((1<<10)-1)^(1<<k));
			}
		for (int i=n-1;i>=0;--i)
			for (int j=1;j<=len;++j)
			{
				dp2[i][j]=0;
				for (int k=0;k<=9;++k)
					if (i+k*pw10[j-1]<=n-1)
						dp2[i][j]|=dp2[i+k*pw10[j-1]][j-1]&(((1<<10)-1)^(1<<k));
			}
		for (int i=0;i<=n-2;++i)
			if (F[dp[i][len]][dp2[i+1][len]]!=inf)
				ans=min(ans,max(F[dp[i][len]][dp2[i+1][len]],1ll)*pw10[len]+pw10[len]-i-1);
		for (int i=1;i<pw10[len];++i)
			if (query(i,i+n-1))
				ans=min(ans,(long long)(i));
		for (int i=0;i+n-1<pw10[len];++i) d=calc(len,i,i+n-1,0),ans=min(ans,max(F[d][d],1ll)*pw10[len]+i);
		printf("%lld\n",ans);
	}
	return 0;
}