Minimum Resistor Network

Time limit2sMemory limit128 MB

Summary

Find the minimum number of 1-ohm or 2-ohm resistors combined via series and parallel connections to achieve an exact resistance a/b, capped at 16 or else -1.

Level: Hard8 of 10
Topics: Math, Recursion, Backtracking, Number theory
Solved: No attempts yet

Problem

You have many resistors whose resistance is either 1 or 2.

When several resistors are connected in series, their equivalent resistance is the sum of their resistances. For example, resistors with values R1, R2, R3, ..., Rn connected in series have equivalent resistance R1 + R2 + R3 + ... + Rn.

When several resistors are connected in parallel, their equivalent resistance is the reciprocal of the sum of reciprocals: 1 / ((1 / R1) + (1 / R2) + (1 / R3) + ... + (1 / Rn)).

Given two positive integers a and b, connect resistors in series and parallel so that the equivalent resistance is exactly a / b. Find the minimum number of resistors needed.

Input

The first line contains two positive integers a and b. Both are at most 50,000.

Output

Print the minimum number of resistors needed on the first line. If more than 16 resistors are required, print -1.

Hint

To make 6 / 5, first connect resistors of values 1 and 2 in series to make value 3. Then connect that result in parallel with a resistor of value 2.

Examples6

Example 1
Input
```
6 5
```
Expected output
```
3
```
Example 2
Input
```
1 1
```
Expected output
```
1
```
Example 3
Input
```
2 3
```
Expected output
```
2
```
Example 4
Input
```
42 47
```
Expected output
```
7
```
Example 5
Input
```
1 20
```
Expected output
```
-1
```
Example 6
Input
```
756 874
```
Expected output
```
10
```