Cercetatorii de la NASA au descoperit un microorganism format din N celule. Asupra acestui organism ei au descoperit ca pot sa aplice doua tipuri de operatii:
1. Divizare. Fiecare celula a microorganismului este divizata în P celule (P fiind numar prim).
2. Combinare. Se formeaza grupuri de câte T celule (T fiind de asemenea numar prim), celulele din fiecare grup combinându-se într-o singura celula. T trebuie sa fie ales astfel încât operatia sa fie posibila.

Cerinţă

Scrieti un program care sa determine numarul minim de operatii ce trebuie sa fie aplicate pentru a transforma un microorganism cu N celule într-un microorganism cu M celule.

Date de intrare

Fisierul de intrare celule.in contine pe prima linie numerele naturale N si M separate prin spatiu.

Date de ieşire

Fisierul de iesire celule.out va contine o singura linie pe care va fi scris un singur numar natural reprezentând numarul minim de operatii ce trebuie sa fie aplicate pentru a transforma un microorganism cu N celule într-un microorganism cu M celule.

Restricţii

• 1<= N, M <= 10⁹

Exemple

celule.in	celule.out	Explicaţii
2 15	3	Pentru a transforma microorganismul cu 2 celule într-unul cu 15 celule se poate proceda astfel: Divizare cu P=5 rezulta un microorganism cu 10 celule Combinare cu P=2 rezulta un microorganism cu 5 celule Divizare cu P=3 rezulta un microorganism cu 15 celule

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com