Fractiles (Small)

Problem

Long ago, the Fractal civilization made artwork from straight rows of tiles. They used two kinds of tile: gold (G) and lead (L).

Each piece of Fractal artwork depends on two parameters: an original sequence of $K$ tiles and a complexity $C$ . For a given original sequence, the artwork of complexity 1 is the original sequence itself, and the artwork of complexity $X+1$ is built from the artwork of complexity $X$ as follows:

replace each L tile in the complexity $X$ artwork with another copy of the original sequence
replace each G tile in the complexity $X$ artwork with $K$ G tiles

For example, for the original sequence LGL, the artwork of complexity 1 to 3 is:

$C = 1$ : LGL (the original sequence itself)
$C = 2$ : LGLGGGLGL
$C = 3$ : LGLGGGLGLGGGGGGGGGLGLGGGLGL

You have just discovered a piece of Fractal artwork, but the tiles are too dirty for you to tell what they are made of. You are an archaeologist who knows the local Fractal culture well, so you know the values of $K$ and $C$ for the artwork, but you do not know the original sequence. Gold is exciting, so you want to know whether the artwork contains at least one G tile. Your budget lets you hire $S$ graduate students. Each of them can clean one tile of your choice (out of the $K^C$ tiles in the artwork) to see whether that tile is G or L.

Can you choose a set of at most $S$ specific tiles to clean so that, whatever the original sequence was, you will know for sure whether at least one G tile is present in the artwork? If so, which tiles should you clean?

Input

The first line of the input gives the number of test cases, $T$ . $T$ test cases follow. Each consists of one line with three integers $K$ , $C$ , and $S$ .

Limits

$1 \le T \le 100$
$1 \le K \le 100$
$1 \le C \le 100$
$K^C \le 10^{18}$
$1 \le S \le K$

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1). If no set of at most $S$ tiles answers your question, y is IMPOSSIBLE. Otherwise y is the list of positions of the tiles to clean. Tiles are numbered from 1 for the leftmost tile to $K^C$ for the rightmost tile.

Several sets of tiles can answer the question, so output this one: take a set with the fewest tiles, and among all such sets, take the one whose positions, sorted in increasing order, form the lexicographically smallest list. Print its positions in increasing order, separated by single spaces.

Hint

In sample case #1, there are four possible original sequences: GG, GL, LG, and LL. They produce the following artwork:

Original sequence GG: GGGGGGGG
Original sequence GL: GGGGGGGL
Original sequence LG: LGGGGGGG
Original sequence LL: LLLLLLLL

Looking at tile #2 alone is enough. If tile #2 is G, you know for sure that the artwork contains a G. (You will not know whether the original sequence is GG, GL, or LG, but that does not matter.) If tile #2 is L, the original sequence must be LL, so the artwork has no G.

Tile #1 alone is not enough. If it is L, the original sequence could be either LG or LL. The first has a G in the artwork and the second does not. So the answer is 2. The set 1 2 also answers the question, but it uses more tiles than necessary, so it is not the required output. 1 2 3 is not valid at all, because it uses too many tiles.

In sample case #2, the artwork is a single tile, either G or L. Looking at that tile tells you directly whether the artwork has a G.

In sample case #3, the artwork is GG, GL, LG, or LL. You can look at only one tile, and neither tile is enough on its own. If tile #1 is L, the artwork could be LG or LL, so you cannot tell whether a G is present. If tile #2 is L, the artwork could be GL or LL, so again you cannot tell.

Sample case #4 is like sample case #3, but you can look at one more tile. Now you can look at the entire artwork.

In sample case #5, there are eight possible original sequences, and they produce the following artwork:

Original sequence GGG: GGGGGGGGG
Original sequence GGL: GGGGGGGGL
Original sequence GLG: GGGGLGGGG
Original sequence GLL: GGGGLLGLL
Original sequence LGG: LGGGGGGGG
Original sequence LGL: LGLGGGLGL
Original sequence LLG: LLGLLGGGG
Original sequence LLL: LLLLLLLLL

No single tile answers the question, so at least two tiles are needed. Tiles #1 and #6 work: if both are L, the artwork is all L, and otherwise it has at least one G. The set 1 2 does not work, because even if both tiles are L, the original sequence could still be LLG. The set 2 6 also works, but the list 1 6 is lexicographically smaller, so the answer is 1 6.