The tell-tale heart P46494

The old man was dead…First of all I dismembered the corpse. I cut off the head and the arms and the legs…There was nothing to wash out –no stain of any kind –no blood-spot whatever. I had been too wary for that. A tub had caught all –ha! ha!

So our hero has a big tub full with the blood of the old man he has just killed. He also has several empty smaller tubs, where (in his madness) he has decided to distribute the blood to hide it from the policemen that will arrive soon to investigate. Every tub has an exact integer capacity. Obsessed with details, our hero wants to distribute the blood evenly among all the tubs, included the bigger tub that now contains all the blood. To achieve this, and as many times as he likes, all he can do is to choose any non-empty tub x and any other non-full tub ‍y, and pour blood from x into y until x becomes empty, or until y becomes full (or both).

Our hero can already hear the hearts of some policemen approaching his home’s door, so he will have to rush! Please help this nice gentleman, telling him the minimum number of movements needed to reach a situation where all the tubes have exactly the same quantity of blood.

Input

Input consists of several cases, one per line. Each line has between 1 and 10 integer numbers for the capacities of the tubs, all between 1 and 20. The first number of every case is the capacity of the larger tub, initially full with blood. All the numbers of the same case are different. Every given case is either unsolvable or solvable in at most 10 movements.

Output

For every case, print its number, followed by the minimum number of movements needed to evenly distribute the blood. If it is impossible, state so.

Hint

A plain brute-force solution should be much too slow for this problem.