Slides! (Large)

Gooli is a huge company that owns $B$ buildings in a hilly area. The buildings are numbered from 1 to $B$.

The CEO wants to build a set of slides between buildings that she can use to travel from her office in building 1 to her favorite cafe in building $B$. Slides are one-way only, but the buildings are tall and have elevators, so a slide can start in any building and end in any other building, and can go in either direction. Specifically, for any two buildings $x$ and $y$, you can build either zero or one slides from $x$ to $y$, and you can build either zero or one slides from $y$ to $x$. The exception is that no slides are allowed to originate in building $B$, since once the CEO reaches that building, she has no need to slide any further.

In honor of Gooli becoming exactly $M$ milliseconds old, the design must give the CEO exactly $M$ different ways to travel from building 1 to building $B$ using the new slides. A way is a sequence of buildings that starts with building 1, ends with building $B$, and has the property that for each pair of consecutive buildings $x$ and $y$ in the sequence, a slide exists from $x$ to $y$. The CEO does not require that every building be reachable from every other building via slides.

Build a set of one or more slides that satisfies the CEO's requirements, or determine that it is impossible.

The first line of the input gives the number of test cases, $T$. $T$ lines follow; each consists of two integers $B$ and $M$, as described above.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is POSSIBLE if the CEO's requirements can be fulfilled and IMPOSSIBLE otherwise.

If it is possible, output an additional $B$ lines containing $B$ characters each, representing a matrix of slides. The $j$-th character of the $i$-th of these lines (with both $i$ and $j$ counting from 1) is 1 if a slide is built from building $i$ to building $j$, and 0 otherwise.

So that the answer is unique, the matrix must be built by this rule:

• For every pair $2 \le i < j \le B$, build a slide from building $i$ to building $j$. Build no other slides among buildings $2$ to $B$.
• If $M = 2^{B-2}$, build a slide from building 1 to each of buildings $2, 3, \ldots, B$.
• If $M < 2^{B-2}$, then for each $k$ with $0 \le k \le B-3$, build a slide from building 1 to building $B-1-k$ exactly when the bit of value $2^k$ in the binary representation of $M$ is 1.
• Build no other slides. In particular, the $i$-th character of the $i$-th line and every character of the last line are 0.

The matrix built by this rule has exactly $M$ ways from building 1 to building $B$.

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

In Case #1 ($B = 5$, $M = 4$), $M < 2^3$ and only the bit of value $2^2$ is set in $M$, so building 1 gets a single slide, to building $5-1-2 = 2$. The four ways to get from building 1 to building 5 are:

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

In Case #3, building slides from 1 to 2, 2 to 3, 3 to 1, and 1 to 4 would create infinitely many ways for the CEO to reach building 4 (she could go directly to 4, or go around the loop once and then go to 4, or go around the loop twice, and so on), but the CEO requested exactly 20 ways.