우로보로스 뱀

우로보로스(Ouroboros)는 고대 이집트 신화에 나오는 뱀으로, 자신의 꼬리를 물고 끊임없이 스스로를 삼킨다.

우로보로스 수(Ouroboros number)는 $2^n$개의 비트로 이루어진 이진수 중에서 $0$부터 $2^n-1$까지의 모든 수를 "생성"하는 성질을 가진 수이다. 생성 과정은 다음과 같다. 우로보로스 수의 $2^n$개 비트를 원형으로 배치한 뒤, 시작 위치를 한 칸씩 옮겨 가며 원을 따라 연속한 $n$개의 비트 묶음을 $2^n$개 읽는다. 이렇게 만든 원을 크기 $n$에 대한 우로보로스 원(Ouroboros circle)이라 부른다. 각 $n$에 대해 우리는 가장 작은 우로보로스 수만을 다룬다.

예를 들어 $n = 2$일 때 우로보로스 수는 $0011$, $0110$, $1100$, $1001$의 네 개뿐이며, 이 중 가장 작은 수는 $0011$이다. 아래 그림은 $0011$에 대한 우로보로스 원이다.

함수 $o(n; k)$는 크기 $n$의 가장 작은 우로보로스 수로 만든 우로보로스 원에서 위치 $k$부터 시작하는 묶음이 나타내는 값을 돌려준다. 위치는 $0$부터 세며, 위치 $k$에서 시작해 원을 따라 연속한 $n$개의 비트를 읽어 이진수로 해석한다(시작 위치 $k$의 비트가 최상위 비트). 여러분의 프로그램은 이 함수 $o(n; k)$를 계산해야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 정수 $n$과 $k$가 주어지는 한 줄로 구성된다($1 \le n \le 15$, $0 \le k < 2^n$). 입력의 끝은 두 개의 $0$이 적힌 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 $o(n; k)$의 값을 한 줄에 하나씩 출력한다.