Measure With Two Jugs

You need exactly target litres of water, but all you have is a tap and two jugs with no markings: jug A holds a litres and jug B holds b litres. Both start empty. One step is one of these:

• fill a jug to the top from the tap;
• empty a jug onto the ground;
• pour from one jug into the other until the first is empty or the second is full, whichever comes first.

Write fewest_steps(a, b, target) that returns the fewest steps after which one of the jugs holds exactly target litres, 0 if target is 0, or -1 if it cannot be done.

Examples

fewest_steps(3, 5, 4)    # returns 6
fewest_steps(2, 6, 5)    # returns -1
fewest_steps(4, 9, 9)    # returns 1

In the first example, writing the jugs as (A, B): fill B (0, 5), pour B into A (3, 2), empty A (0, 2), pour B into A (2, 0), fill B (2, 5), pour B into A (3, 4). B now holds 4 litres after 6 steps. In the second example every amount you can ever make is even.

Constraints

• 1 <= a, b <= 10,000
• 0 <= target <= 10,000
• The target must end up inside one jug: the water in both jugs together does not count.