UVA Solution for 11089

//11089
#include<stdio.h>

int fib[] = {
    1,2,3,5,8,13,21,34,55,89,144,233,377,610,
987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,
196418,317811,514229,832040,1346269,2178309,3524578,5702887,
9227465,14930352,24157817,39088169,63245986,102334155,
165580141,267914296,433494437,701408733,1134903170
};

int main()
{
    int i,j,t,s,sz,n;
    scanf("%d",&t);
    for(i=0;i<t;i++)
    {
    scanf("%d",&n);
   
    {
    for(j = 43; j >= 0; j--)
    {
    if(n>=fib[j])
    break;
    }
         sz = 1;
        s= fib[j];
        putchar('1');
        //printf("1");
       
                
                   
                   for(j--; j>=0; j--)
        {
            if(fib[j] + s <= n && sz)
            {
                putchar('1');
                    //printf("1");
                s +=fib[j];
                sz = 0;
                continue;
            }
                                    else
             putchar('0');
                 //printf("0");
            sz = 1;
   }
                 
                  putchar('\n');
                      //printf("\n");
                    }            
                    }      
  
    return 0;
}