Maximum Prime Factor

Cerință

Fie $X$ un număr natural nenul și $p$ cel mai mare factor prim din descompunerea în factori primi a lui $X$. Pentru $X = 1$, considerăm $p = 1$. Asupra lui $X$ se pot efectua următoarele două operații:

Operația 1: $X$ se împarte la $p$ și devine $X/p$.
Operația 2: $X$ devine $X \cdot k$, unde $k$ este un număr prim și mai mare sau egal decât $p$.

Se dau $Q$ perechi de numere naturale nenule $(X,Y)$. Să se determine, pentru fiecare pereche, numărul minim de operații necesare pentru a îl transforma pe $X$ în $Y$.

Date de intrare

Datele de intrare conțin $Q + 1$ linii. Pe prima linie se găsește $Q$, reprezentând numărul de perechi $(X, Y)$. Pe următoarele $Q$ linii, câte o pereche de numere naturale nenule $X$ și $Y$, despărțite printr-un singur spațiu.

Date de ieșire

Ieșirea va conține $Q$ linii. Pe fiecare linie $i$ se va scrie câte un număr natural reprezentând numărul de operații determinat pentru a $i$-a pereche.

Restricții și precizări

• $1 \leq Q \leq 1 \ 000 \ 000$;
• $1 \leq X, Y \leq 4 \ 000 \ 000$;
• Această problemă are scoruri individuale pe teste.

Exemplu

stdin

4
4 10 
2 9
6 2 
12 12

stdout

2
3
1
0

Explicație

Pentru $(4, 10)$: $4$ devine $2$ utilizând o Operație 1, apoi devine $10$ utilizând o Operație 2.
Pentru $(2, 9)$: $2$ devine $1$ utilizând o Operație 1, apoi devine $3$ folosind o Operație 2 și devine $9$ folosind o Operație 2.
Pentru $(6, 2)$: $6$ devine $2$ folosind o Operație de tip 1.
Pentru $(12, 12)$: Numerele sunt egale, nu este necesară nicio operație.