#include<stdio.h>
#include<stdlib.h>

int main()
{
    int N;
    while( scanf( "%d", &N ) != EOF )
    {
        int x;
        for( x = 1 ; x <= N ; x++ )
        {
            int n;
            scanf( "%d", &n );

            if( n == 0 )
            {
                printf( "Case #%d: 0\n", x );
                continue;
            }

            int b[50] = {0}, bnum = 0;
            int ntemp = abs( n );
            while( ntemp )
            {
                b[bnum++] = ntemp % 2;
                ntemp /= 2;
            }

            int negorpos = ( n > 0 )? 0 : 1;
            int carry = 0;
            int i;
            for( i = 0 ; i < bnum ; i++ )
            {
                int temp = carry;
                carry = ( b[i] + temp ) / 2;
                b[i] = ( b[i] + temp ) % 2;
                if( i % 2 != negorpos && b[i] )
                    carry++;
            }
            if( carry )
            {
                if( i % 2 != negorpos )
                {
                    b[bnum++] = 1;
                    b[bnum++] = 1;
                }
                else
                    b[bnum++] = 1;
            }

            printf( "Case #%d: ", x );
            for( i = bnum-1 ; i >= 0 ; i-- )
                printf( "%d", b[i] );
            printf( "\n" );
        }
    }
    return 0;
}