Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

La gran máquina de deducciones! En eso trabajan BitOne y BitZero esta vez, ellos creen que la máquina será capaz de deducir si $P = NP$ o no. Como siempre, algo les falta, y es que para construirla necesitan un componente electrónico especial de resistencia exactamente $\frac{A}{B}$. Ellos saben construir componentes, pero tienen un presupuesto limitado que les alcanza solamente para conseguir $N$ componentes de resistencia igual a 1 o 2 cada uno. Los componentes se pueden combinar de dos manera diferentes: en serie o en paralelo. Supongamos que tenemos $K$ componentes de resistencias $R_1, R_2, ..., R_k$, si estos componentes se combinan en serie, entonces se obtiene un componente con resistencia exactamente igual a la suma de las resistencias de todos los componentes combinados, o sea, $R_1+R_2+...+R_k$; por el contrario, si se combinan los $K$ componentes en paralelo, entonces el componente resultante tendrá una resistencia igual al inverso de la suma de los inversos de las resistencias de los componentes combinados, esto es, $\displaystyle\frac{1}{\frac{1}{R_1} + \frac{1}{R_2} + ... + \frac{1}{R_k}}$. Todo parece indicar que el problema $P = NP$ se ha reducido a saber si es posible obtener un componente de resitencia $\frac{A}{B}$ con el presupuesto de BitZero y BitOne.

1ra línea : dos enteros $A$ y $B$ $(1 \le A, B \le 50000)$ indicando el numerador y el denominador respectivamente del valor de resistencia requerido.
En el primer subproblema se cumple $N = 10$.
En el segundo subproblema se cumple $N = 16$.

1ra línea : Un entero, la cantidad mínima necesaria de componentes (si es posible con a lo sumo $N$ componentes) o -1.

Hint
En el tercer ejemplo, se combinan en serie dos componentes con resistencias igual a 1 y 2 respectivamente, y luego el componente resultante se combina en paralelo con otro componente de resistencia igual a 2.