ITSA18

 
#include<stdio.h>
int main(){
int n,a=0,b=1,c=1,fib[20000],top=0;
while(c<=100000000){
fib[top++]=c;
c=a+b;
a=b;
b=c;
}
scanf("%d",&n);
while(n--){
    int num,i;
    scanf("%d",&num);
    printf("%d = ",num);
    for(i=top-1;fib[i]>num;i--);
    while(i>0){
        if(num-fib[i]>=0){
                printf("1");
                num-=fib[i];
        }
        else
        printf("0");
        i--;
    }
    printf(" (fib)\n");
}
return 0;
}