Задачі
Система числення "-2"
Система числення "-2"
\textit{Творець створив Всесвіт загадковим чином. При цьому він використовував десяткову систему числення та полюбляв круглі цифри.}
\textit{Скотт Адамс}
Багато людей знають про систему числення з основою \textbf{2} (двійкова система числення) і практично всі знають про десяткову систему числення (система з основою \textbf{10}), а що це за дивна база з основою "\textbf{-2}"? Ціле число \textbf{n} записане у системі числення з основою "\textbf{-2}" це послідовність цифр (\textbf{b_i}), записаних зправа-наліво. Причому кожна цифра це або \textbf{0} або \textbf{1} (не від'ємні цифри!), і при цьому повинна виконуватись рівність:
\textbf{n} = \textbf{b_0} + \textbf{b_1}(\textbf{-2}) + \textbf{b_2}(\textbf{-2})^2 + \textbf{b_3}(\textbf{-2})^3 + ...
Виявляється, що довільне ціле число, у тому числі і від'ємні числа, мають унікальне подання у такій системі числення з основою "\textbf{-2}". Ваша задача - знайти це подання.
\InputFile
У першому рядку задано кількість тестових випадків \textbf{n} (не більше \textbf{10000}). Наступні \textbf{n} рядків містять самі тести у яких знаходиться єдине ціле число в межах від \textbf{-1000000000} до \textbf{1000000000}.
\OutputFile
Для кожного теста в окремому рядку виведіть спочатку повідомлення про йогономер "\textbf{Case #x:}", а далі через проміжок представлення заданого числа у системі числення з основою "\textbf{-2}" без ведучих нулів.
Вхідні дані #1
4 1 7 -2 0
Вихідні дані #1
Case #1: 1 Case #2: 11011 Case #3: 10 Case #4: 0