Inspectoratul școlar județean organizează un concurs pentru ocuparea strategicului post de fochist. La proba de informatică, cea mai importantă a concursului, candidații au de rezolvat următoarea problemă.

Cerința

Se dau n perechi de numere naturale și pentru fiecare pereche (x,y) trebuie să se afle câte numere naturale nenule strict mai mici decât produsul x * y sunt prime cu x * y.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n perechi de numere naturale x și y.

Date de ieșire

Programul va afișa pe ecran, pentru fiecare pereche (x, y) valoarea cerută, urmată de enter.

Restricții și precizări

• 1 ≤ n ≤ 10.000
• Pentru fiecare pereche (x, y), 2 ≤ x, y ≤ 200.000
• Două numere sunt prime între ele dacă cel mai mare divizor al lor este 1.
• Atenție, produsul a două numere poate depăși valoarea maximă admisă de tipul int.
• Această ultimă precizare este disponibilă numai inspectorilor.

Exemplu:

Intrare

3
3 4
3 3
97 33

Ieșire

4
6
1920

Explicație

Pentru prima pereche: 3 * 4 = 12, iar 12 este prim cu patru numere: 1, 5, 7, 11. Pentru a doua pereche: 3 * 3 = 9, iar 9 este prim cu șase numere: 1, 2, 4, 5, 7, 8. Pentru a treia pereche: puteți verifica și singuri că așa este. Oricum, inspectorii nu greșesc niciodată.