Problem G
Filling Crates

A single $5\times 10$ crate holding $50$ bottles of jubileumsöl. S:t Eriks bryggeri, Stockholm, 1953.

Ada the Alewife wants to ship $n$ beers from her brewery, all neatly packed into as few crates as possible. Crates come in many different sizes: For integers $a, b$ with $a\geq 2$ and $b\geq 2$, a single crate of size $a\times b$ holds exactly $a\cdot b$ beers. Note that no crate has side length $1$.

For instance, $67$ beers can be packed into two crates, one of size $7\times 7$ and one of size $3\times 6$, because $7\cdot 7 + 3\cdot 6 = 49 + 18 = 67$, like this:

On the other hand, there is no way to pack $67$ beers into just a single crate without leaving empty slots; here are some failed attempts:

Input

A single integer $n$ with $4\leq n\leq 1\, 000$, the number of beers that Ada needs to pack.

Output

A sequence of crate sizes, each given as $a_ i\texttt{x}b_ i$, separated by space, and such that $a_1\cdot b_1+\cdots + a_ k\cdot b_ k = n$. The number $k$ of crates must be minimised.

If the $n$ beers cannot be packed, write ‘impossible’.

If there is more than one valid answer, any of them will do. The order of crates and crate sizes is not important.

7

impossible

10

2x5

67

7x7 6x3