Oblicz liczbę ułamków a/b ( 1 <= a, b <= N ) takich, że istnieją liczby całkowite c, d ( 1 <= c, d <= M ), że a/b = c/d.

입력 형식

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ).</p>

W każdej z kolejnych Z linii znajdują się 2 liczby całkowite N (1<=N<=1000000) i M (1<=M<=N).

출력 형식

Dla każdego zestawu testowego wypisz szukaną ilość ułamków.

예제 입력

1
3 2

예제 출력

5

힌트

Szukane ułamki z przykładu to: 1/1, 1/2, 2/1, 2/2, 3/3