const mo=;

 var f:array[..,..,..,..]of longint;

     g:array[..,..,..]of longint;

     a:array[..]of longint;

     v,n,i,j,k,l,jj,kk,ans,cas,ll:longint;

     ch:string;

 begin

  readln(cas);

  for v:= to cas do

  begin

   readln(ch);

   n:=length(ch);

   for i:= to n do a[i]:=;

   for i:= to n do a[i]:=ord(ch[i])-ord('');

   for i:= to n do

    for j:= to  do

     for k:= to  do

      for l:= to  do f[i,j,k,l]:=;

   for i:= to a[]- do f[,i,,]:=;

   f[,a[],,]:=;

   for i:= to n do

    for j:= to  do

     for k:= to  do

      for l:= to  do

       for jj:= to  do

       begin

        if k= then kk:=;

        if (k=)and(jj<a[i]) then kk:=;

        if (k=)and(jj=a[i]) then kk:=;

        if (k=)and(jj>a[i]) then break;

        for ll:=l to  do

        begin

         if (ll=)and(j<jj) then continue;

         if (ll=)and(j>jj) then continue;

         if (ll<>l)and(j=jj) then continue;

         f[i,jj,kk,ll]:=(f[i,jj,kk,ll]+f[i-,j,k,l]) mod mo;

        end;

       end;

   for i:= to n- do

    for j:= to  do

     for k:= to  do g[i,j,k]:=;

   for i:= to  do g[,i,]:=;

   for i:= to n- do

     for j:= to  do

      for k:= to  do

       for jj:= to  do

        for kk:=k to  do

        begin

         if (kk=)and(j<jj) then continue;

         if (kk=)and(j>jj) then continue;

         if (k<>kk)and(j=jj) then continue;

         g[i,jj,kk]:=(g[i,jj,kk]+g[i-,j,k]) mod mo;

        end;

   ans:=;

   for j:= to  do

    for k:= to  do

     for l:= to  do ans:=(ans+f[n,j,k,l]) mod mo;

   for i:= to n- do

    for j:= to  do

     for k:= to  do ans:=(ans+g[i,j,k]) mod mo;

   writeln(ans);

  end;

 end.