-2진법 변환

자리 표기법에서 맨 오른쪽 자리의 자리값은 $b^0 = 1$이고, 왼쪽으로 한 칸 갈 때마다 밑 $b$가 한 번 더 곱해져서 $b^1$, $b^2$, ... 로 커진다. 밑이 $-2$이면 자리값은 오른쪽부터 차례로 $1, -2, 4, -8, 16, -32, \dots$ 이다. 그래서 1부터 하나씩 세어 올라가면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 순서로 이어진다.

$-2$진법은 부호 비트를 따로 두지 않고 음수를 나타낸다. 십진수 $N$을 $-2$진법으로 바꿔 출력하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $T$는 양의 정수이고 $T \le 100000$이다.

이어지는 $T$개의 줄에 각각 정수 $N$이 하나씩 주어진다. $-10^{17} \le N \le 10^{17}$이다.

각 테스트 케이스마다 Case #x: M 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $M$은 $N$의 $-2$진법 표현이다.

$M$ 앞에는 0을 붙이지 않는다. $N = 0$이면 0만 출력한다.