#include<stdio.h>
#include<string.h>
int comparare(int a[],int b[])
{
 int i;
 if(a[0]>b[0]) return 1;
 else
	if(a[0]<b[0]) return 2;
	else
	{
		i=a[0];
		while(a[i]==b[i]&&i>0)
			i--;
			if(i==0) return 0;
			else
			 if(a[i]>b[i]) return 1;
			 else return 2;
	}
}
int main()
{
 int t,i,j,q,p,aux;
 FILE *in=fopen("cifra.in","rt");
 FILE *out=fopen("cifra.out","wt");
 char s[102];
 int nr[102],n[102],v[102];
 fscanf(in,"%d",&t);
 for(i=1;i<=t;i++)
 {
	 fscanf(in,"%s",s);
	 p=strlen(s);
	 for(j=0;j<p;j++)
		n[p-j]=s[j]-'0';
	 n[0]=p;
	 for(int k=0;k<=101;k++) v[k]=0;
	 v[1]=1;v[0]=1;
	 for( ;comparare(v,n)!=0; )
	 {
		t=v[1]+1;
		v[1]=t%10;
		t=t/10;
		for(k=2;k<=v[0];k++)
		{
		 t=t+v[k];
		 v[k]=t%10;
		 t=t/10;
		}
		if(t>0) {v[0]++;v[v[0]]=t;}
	 }
 }
 return 0;
}