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

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 ≤ 107
  • 1 ≤ G ≤ M

Exemplu

divagain.in divagain.out
2
42 2
5 1
4
2

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).

Trebuie să te autentifici pentru a trimite soluții. Click aici