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 * k, unde k este un număr prim și mai mare sau egal decât p.

Cerința

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 ≤ Q ≤ 1.000.000
• 1 ≤ X, Y ≤ 4.000.000
• Datorită dimensiunii mari a datelor de intrare și de ieșire, doar unele teste au fost adăugate.

Exemplu:

Intrare

4
4 10
2 9
6 2
12 12

Ieșire

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.