미끄럼틀! (Large)

Gooli는 언덕 지대에 건물 $B$개를 소유한 대기업이다. 건물에는 1부터 $B$까지 번호가 붙어 있다.

CEO는 1번 건물에 있는 사무실에서 $B$번 건물에 있는 단골 카페까지 이동할 때 쓸 미끄럼틀을 건물 사이에 설치하려고 한다. 미끄럼틀은 당연히 한 방향으로만 이용할 수 있다. 하지만 건물이 높고 엘리베이터가 있으므로 미끄럼틀은 어느 건물에서 출발해 다른 어느 건물에서든 끝날 수 있고, 방향도 자유롭다. 정확히 말하면 서로 다른 두 건물 $x$, $y$에 대해 $x$에서 $y$로 가는 미끄럼틀은 0개 또는 1개 설치할 수 있고, $y$에서 $x$로 가는 미끄럼틀도 0개 또는 1개 설치할 수 있다. 단, $B$번 건물에서 출발하는 미끄럼틀은 설치할 수 없다. CEO가 그 건물에 도착하면 더 미끄러질 필요가 없기 때문이다.

Gooli가 생긴 지 정확히 $M$밀리초가 된 것을 기념해서, 새 미끄럼틀로 1번 건물에서 $B$번 건물까지 가는 방법이 정확히 $M$가지가 되도록 설계해야 한다. 방법이란 1번 건물로 시작해 $B$번 건물로 끝나는 건물의 수열로, 수열에서 연속한 두 건물 $x$, $y$마다 $x$에서 $y$로 가는 미끄럼틀이 있어야 한다. CEO는 모든 건물 사이가 미끄럼틀로 서로 닿을 것을 요구하지 않는다.

CEO의 요구를 만족하는 미끄럼틀 집합(미끄럼틀 1개 이상)을 만들거나, 불가능하다는 것을 판정하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 다음 $T$개의 줄에는 각각 위에서 설명한 두 정수 $B$와 $M$이 주어진다.

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 CEO의 요구를 만족할 수 있으면 POSSIBLE, 없으면 IMPOSSIBLE이다.

POSSIBLE이면 그 뒤에 길이 $B$인 줄 $B$개를 더 출력한다. 이 행렬에서 $i$번째 줄의 $j$번째 문자($i$, $j$는 1부터 센다)는 건물 $i$에서 건물 $j$로 가는 미끄럼틀을 설치하면 1, 아니면 0이다.

답이 하나로 정해지도록 행렬은 반드시 다음 규칙대로 만든다.

• $2 \le i < j \le B$인 모든 쌍에 대해 건물 $i$에서 건물 $j$로 가는 미끄럼틀을 설치한다. 건물 $2$부터 $B$ 사이의 다른 미끄럼틀은 설치하지 않는다.
• $M = 2^{B-2}$이면 건물 1에서 건물 $2, 3, \ldots, B$ 모두로 가는 미끄럼틀을 설치한다.
• $M < 2^{B-2}$이면 $0 \le k \le B-3$인 각 $k$에 대해 $M$의 이진 표현에서 $2^k$ 자리의 비트가 1일 때만 건물 1에서 건물 $B-1-k$로 가는 미끄럼틀을 설치한다.
• 그 밖의 미끄럼틀은 설치하지 않는다. 따라서 $i$번째 줄의 $i$번째 문자와 마지막 줄의 모든 문자는 0이다.

이 규칙으로 만든 행렬에서 1번 건물에서 $B$번 건물로 가는 방법은 정확히 $M$가지이다.

• $1 \le T \le 100$
• $2 \le B \le 50$
• $1 \le M \le 10^{18}$

예제 1번 케이스($B = 5$, $M = 4$)에서 $M < 2^3$이고 $M$의 $2^2$ 자리 비트만 1이므로 건물 1에서는 건물 $5-1-2 = 2$로 가는 미끄럼틀만 설치한다. 건물 1에서 건물 5로 가는 네 가지 방법은 다음과 같다.

• 1, 2, 5
• 1, 2, 3, 5
• 1, 2, 4, 5
• 1, 2, 3, 4, 5

3번 케이스에서 1에서 2, 2에서 3, 3에서 1, 1에서 4로 가는 미끄럼틀을 설치하면 CEO가 4번 건물에 가는 방법이 무한히 많아진다(곧바로 4로 갈 수도 있고, 고리를 한 바퀴 돈 뒤 4로 갈 수도 있고, 두 바퀴 돈 뒤 갈 수도 있다). 하지만 CEO는 정확히 20가지를 요구했다.