Система счисления "-2"
Творец создал Вселенную загадочным образом. При этом он использовал десятичную систему счисления и любил круглые цифры.
Скотт Адамс
Многие знают о системе счисления с основанием 2 (двоичная система счисления) и практически все знают о десятичной системе счисления (система с основанием 10), а что это за странная база с основанием "-2"? Целое число n записанное в системе счисления с основанием "-2" это последовательность цифр (b_i), записанных справа-налево. Причём каждая цифра это либо 0 либо 1 (не отрицательные цифры!), и при этом должно выполняться равенство:
n = b_0 + b_1(-2) + b_2(-2)^2 + b_3(-2)^3 + ...
Оказывается, что любое целое число, в том числе и отрицательные числа, имеют уникальное представление в такой системе счисления с основанием "-2". Ваша задача - найти это представление.
Входные данные
В первой строке задано количество тестов n (не более 10000). Следующие n строк содержат сами тесты, в которых находится единственное целое число в пределах от -1000000000 до 1000000000.
Выходные данные
Для каждого теста в отдельной строке выведите сначала сообщение о его номере "Case #x:", а далее через пробел представление заданного числа в системе счисления с основанием "-2" без ведущих нулей.