LCM is an abbreviation used for Least Common Multiple in Mathematics. We say LCM(a,b) = L if and only if L is the least integer which is divisible by both a and b. You will be given N, M. You have to count number of pair (i,j) such that LCM(i,j) = i × j, where1≤i≤N and1≤j≤M. Input Input starts with an integer T (≤ 1000), denoting the number of test cases. Each case starts with a line containing two integers N, M (1 ≤ N,M ≤ 109, and the minimum of them min(N,M) ≤ 106). Output For each case, print number of such pair. Sample Input 3 12 42 35 Sample Output 2 6 12