Fișierul intrare/ieșire	divagain.in, divagain.out	Sursă	ad-hoc
Autor	din folclor	Adăugată de	Dragos Alin Rotaru • mathboy
Timp de execuție pe test	0.3 sec	Limită de memorie	8096 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Divagain

Tractorel își pune întrebări existențiale deseori. De data aceasta el se întreabă cum să determine numărul de perechi formate din numere naturale (x, y) pentru care cel mai mare divizor comun al lor este G și cel mai mic multiplu comun este M. El știe că perechea (x, y) diferă de perechea (y, x).
Tractorel, fiind în toane bune, își pune T întrebări ca mai sus și vă roagă pe voi să răspundeți. (ca întotdeauna)

Date de intrare

Fișierul de intrare divagain.in contine pe prima linie un numar natural, T. Pe urmatoarele T linii se află 2 numere naturale separate printr-un spațiu: M, G.

Date de ieșire

În fișierul de ieșire divagain.out se va afla T linii, fiecare linie având cate un număr reprezentând răspunsul la fiecare din cele T intrebări.

Restricții

• 1 ≤ T ≤ 10
• 1 ≤ M ≤ 10⁷
• 1 ≤ G ≤ M

Exemplu

Explicație

Pentru M = 42, G = 2, avem urmatoarele perechi: (6, 14), (14, 6), (2, 42), (42, 2)
Pentru M = 5, G = 1, avem urmatoarele perechi: (1, 5), (5, 1).