Fişierul intrare/ieşire: | divagain.in, divagain.out | Sursă | ad-hoc |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 0.3 sec | Limită de memorie | 8096 kbytes |
Scorul tău | N/A | Dificultate |
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.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).