算法题：UVA 11121 - Base -2 （数论）

算法题：UVA 11121 - Base -2 （数论）2014-04-10 accelerator_ Problem D

Base -2

Input: Standard Input

Output: Standard Output

The creator of the universe works in mysterious ways. But he uses a base ten counting system and likes round numbers.

Scott Adams

Everyone knows about base-2 （binary） integers and base-10 （decimal） integers, but what about base -2？ An integer n written in base -2 is a sequence of digits （b_i）, writen right-to-left. Each of which is either 0 or 1 （no negative digits！）, and the following equality must hold.

n = b₀ + b₁（-2） + b₂（-2）² + b₃（-2）³ + ...

The cool thing is that every integer （including the negative ones） has a unique base- -2 representation, with no minus sign required. Your task is to find this representation.

Input

The first line of input gives the number of cases, N （at most 10000）. N test cases follow. Each one is a line containing a decimal integer in the range from -1,000,000,000 to 1,000,000,000.

Output

For each test case, output one line containing "Case #x:" followed by the same integer, written in base -2 with no leading zeros.

Sample Input Output for Sample Input