Система числення "-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" без ведучих нулів.