Slides! (Small)

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, there is no need for her to do any more sliding.

In honor of Gooli becoming exactly M milliseconds old, the design must ensure that the CEO has 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.

Find 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 contains 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 B more lines of B characters each. They form a matrix that describes the 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 goes from building i to building j, and 0 otherwise. The i-th character of the i-th line is always 0, and every character of the last line is 0.

To make the answer unique, build the slides by this rule:

• For every pair of buildings i and j with $2 \le i < j \le B$, build a slide from building i to building j.
• If $M = 2^{B-2}$, build a slide from building 1 to every other building.
• Otherwise, build no slide from building 1 to building B. For each i with $2 \le i \le B-1$, build a slide from building 1 to building i if the bit of value $2^{B-1-i}$ is set in the binary representation of M, and no slide otherwise.
• Build no other slides.

Whenever the requirements can be fulfilled, this rule produces exactly M ways.

• $1 \le T \le 100$
• $2 \le B \le 6$
• $1 \le M \le 20$

In the first case of sample 1 (B = 5, M = 4), the rule gives these 4 ways to get from building 1 to building 5:

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

In the third case, 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.