\textit{The creator of the universe works in mysterious ways. Buthe uses a base ten counting system and likes round numbers.} \textit{Scott Adams} Everyone knows about base-\textbf{2} (binary) integers and base-\textbf{10} (decimal) integers, but what about base "\textbf{-2}"? An integer \textbf{n} written in base "\textbf{-2}" is a sequence of digits (\textbf{b_i}), writen right-to-left. Each of which is either \textbf{0} or \textbf{1} (no negative digits!), and the following equality must hold. \textbf{n} = \textbf{b_0} + \textbf{b_1}(\textbf{-2}) + \textbf{b_2}(\textbf{-2})^2 + \textbf{b_3}(\textbf{-2})^3 + ... The cool thing is that every integer (including the negative ones) has a unique base-"\textbf{-2}" representation, with no minus sign required. Your task is to find this representation. \InputFile The first line of input gives the number of cases, \textbf{n} (at most \textbf{10000}). \textbf{N} test cases follow. Each one is a line containing a decimal integer in the range from \textbf{-1,000,000,000} to \textbf{1,000,000,000}. \OutputFile For each test case, output one line containing "\textbf{Case #x:}" followed by the same integer, written in base "\textbf{-2}" with no leading zeros.