GCD not equal LCM

GCD not equal LCM

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

We all know that,

GCD means Greatest Common Divisor. For example,

\(GCD ( 4, 10 , 12) = 2\), that means 2 is the largest possible number which divides all number appears in the set.

And, LCM means Least Common Multiple. For example,

\(LCM ( 4, 10, 12 ) = 60 \), that means 60 is the least common multiple of this set.

You are given two integers A and B. You need to find out all possible pair \((i , j)\) such that,

\(1 < = i <= A\) and \(1 < = j <= B,\)

  • \(GCD ( i , j)\) ! = \(LCM ( i , j)\).

Note : ( "! = " means not equal.)

Input

First Line T, the number of test case.
In each test case, two postives integers A and B.

\(1 < = T < = 10^5\)
\(1 < = A , B < = 10^9\)

Output

In each test cases, print the total number of pair satisfy the conditions.

Sample

Input Output
2
1 2
3 2
1
4

First test case explaination:
Only one pair satisfied this condition.

when i = 1 and j = 2,

GCD ( i, j ) = ( 1, 2 ) = 1.

LCM ( i, j ) = ( 1, 2 ) = 2.

GCD (i,j) ! = LCM ( i,j). So answer is 1.

Information

ID
1075
Difficulty
5
Category
Math | Number_Theory , Implementation Click to Show
Tags
# Submissions
18
Accepted
13
Accepted Ratio
72%
Uploaded By

Related

In following contests:

Brain Booster #5