Fișierul intrare/ieșire divagain.in, divagain.out Sursă ad-hoc
Autor din folclor Adăugată de avatar mathboy Dragos Alin Rotaru mathboy
Timp de execuție pe test 0.3 sec Limită de memorie 8096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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