Base -2#1375
Sign in

Base -2

1 second
64 megabytes
Very easy

The creator made the Universe in a mysterious way. At the same time, he used the decimal system and liked round numbers.

Scott Adams

Many people know about the base- (binary system), and almost everyone knows about the base- (decimal system). But what is this strange base called ""? An integer written in base "" is a sequence of digits (b_i), written from right to left. Each digit is either or (no negative digits!), and the following equality must hold:

n = b_0 + b_1(-2)^1 + b_2(-2)^2 + b_3(-2)^3 + \ldots

It turns out that any integer, including negative numbers, has a unique representation in such a base "" system. Your task is to find this representation.

Input

The first line contains the number of test cases (n \leq 10000). Each of the next lines contains a single integer, which lies between and .

Output

For each test case, output a single line starting with the message "Case #x:", followed by the representation of the given number in base "" without leading zeros.

Examples

Example 1

Loading
Loading