Fişierul intrare/ieşire:divagain.in, divagain.outSursăad-hoc
AutorDin FolclorAdăugată demathboyDragos Alin Rotaru mathboy
Timp execuţie pe test0.3 secLimită de memorie8096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile 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.indivagain.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 sa te autentifici pentru a trimite solutii. Click aici