긱 챌린지 [SKRZAT] (밑이 -2인 진법)

긱 챌린지 [SKRZAT]는 두 개의 버튼과 조이스틱이 달린 콘솔로 즐기는 폴란드의 아주 오래된 게임이다. 이름 그대로 이 게임은 이진법으로 소통한다. 한 버튼은 0을, 다른 버튼은 1을 뜻한다. 여기서 한 걸음 더 나아가, 이 게임은 밑(base)이 +2가 아니라 -2인 수 체계를 사용하는데, 이 표현을 “위어드 바이너리(Weird Binary)”라고 부르기로 한다.

위어드 바이너리에서 오른쪽에서부터 $0$번째로 세었을 때 위치 $i$의 비트는 가중치 $(-2)^i$를 가진다. 비트 문자열의 값은 1인 위치들의 가중치를 모두 더한 값이다. 5비트 패턴과 그 값은 다음과 같다.

모든 5비트 패턴을 비트 순서대로 정렬한 표:

같은 값들을 크기 순으로 정렬한 표:

숫자는 화면에 위어드 바이너리로 표시되고, 플레이어는 콘솔에서 0과 1의 흐름으로 답한다. 십진수와 위어드 바이너리 사이를 변환하여 초보자를 돕는 프로그램을 작성하라.

첫 번째 줄에는 질의의 개수를 나타내는 정수 $n$이 주어진다. 이어지는 $n$개의 줄이 각각 하나의 질의이다.

• b로 시작하는 줄에는 십진수로 변환해야 하는 위어드 바이너리 문자열이 들어 있다.
• d로 시작하는 줄에는 위어드 바이너리로 변환해야 하는 십진수 정수가 들어 있다.

모든 값은 15비트 위어드 바이너리로 표현할 수 있으므로, 십진수 범위는 $-10922$ 이상 $21845$ 이하이다.

각 질의마다 한 줄씩 출력한다. 질의 종류와 입력 문자열, 그리고 변환 결과를 함께 보여 준다.

• b 질의의 경우: From binary: <문자열> is <십진수>
• d 질의의 경우: From decimal: <문자열> is <위어드 바이너리>

입력 문자열은 그대로 다시 출력한다(위어드 바이너리 입력에는 앞자리 0이 있을 수 있다). 출력하는 위어드 바이너리 결과에는 앞자리 0을 붙이지 않으며, 값 $0$은 0으로 적는다. 위에 보인 간격을 정확히 그대로 맞춘다.