3332 - GCD and LCM

Created by Alfredo Fundora Rolo
Added by alfredo12345 (2015-06-15)
Limits
Total Time: 5000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Tom and Jerry decided to make a day of truce to sit back and play. As they are attracted to mathematical problems related to the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM), they chose to solve a similar problem: they want to find how many unordered pairs of positive integers A and B are there such that GCD of A and B is N and the LCM of A and B is M.
  • The GCD of two positive integers is defined as the largest integer that evenly divides both integers.
  • The LCM of two positive integers is defined as the smallest positive integer that is divisible by both integers.
Note that a positive integer can be the GCD or LCM of many pairs of numbers. In an unordered pair, order is not taken into account, that is, the pair (A, B) is the same as (B, A) and should be counted only once.
Tom y Jerry decidieron hacer un día de tregua para sentarse y jugar. A medida que se sienten atraídos por los problemas matemáticos relacionados con el Máximo Común Divisor (GCD, por sus siglas en Inglés) y el Mínimo Común Múltiplo (LCM, por sus siglas en Inglés), eligieron para resolver un problema similar: quieren encontrar cuántos pares no ordenados de números enteros positivos A y B existen tales que el GCD de A y B es N y el LCM de A y B es M.
  • El GCD de dos números enteros positivos se define como el número entero más grande que divide uniformemente ambos enteros.
  • El LCM de dos números enteros positivos se define como el número entero positivo más pequeño que es divisible por ambos enteros.
Note que un entero positivo puede ser el GCD o LCM de muchos pares de números. En un par no ordenado, el orden no se tiene en cuenta, es decir, el par (A, B) es el mismo que (B, A) y debe ser contado sólo una vez.
Tom and Jerry decided to make a day of truce to sit back and play. As they are attracted to mathematical problems related to the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM), they chose to solve a similar problem: they want to find how many unordered pairs of positive integers A and B are there such that GCD of A and B is N and the LCM of A and B is M.
  • The GCD of two positive integers is defined as the largest integer that evenly divides both integers.
  • The LCM of two positive integers is defined as the smallest positive integer that is divisible by both integers.
Note that a positive integer can be the GCD or LCM of many pairs of numbers. In an unordered pair, order is not taken into account, that is, the pair (A, B) is the same as (B, A) and should be counted only once.

Input specification

The first line of input consists of a positive integer T (T <= 100) denoting the number of cases. Each of the next T lines contains two positive integers N and M (1 <= N, M <= 10^9) separated by a single white space.
La primera línea de entrada consta de un número entero positivo T (T <= 100) que indica el número de casos. Cada una de las siguientes T líneas contiene dos números enteros positivos N y M (1 <= N, M <= 10^9) separados por un único espacio en blanco.
The first line of input consists of a positive integer T (T <= 100) denoting the number of cases. Each of the next T lines contains two positive integers N and M (1 <= N, M <= 10^9) separated by a single white space.

Output specification

For each case output a line with the number of unordered pairs of positive integers A and B are there such that GCD of A and B is N and the LCM of A and B is M.
Por cada caso usted debe imprimir una línea con la cantidad de pares no ordenados de números enteros positivos A y B que existen tales que el GCD de A y B es N y el LCM de A y B es M.
The first line of input consists of a positive integer T (T <= 100) denoting the number of cases. Each of the next T lines contains two positive integers N and M (1 <= N, M <= 10^9) separated by a single white space.

Sample input

1
2 4

Sample output

1

Hint(s)