iit-delhi-and-arjit-singh

As we all know cultural fest of IIT-Delhi is one of the biggest youth festival of north india and this year too it was very special as there was live performance
by Arjit Singh.Now as he is very famous star in  india so there was a estimation of huge crowd and campus of IIT-Delhi may fail to handle such a crowd.
So,fest-management team of IIT-Delhi devised a solution by introducing tickets system.But this method failed due to huge demand of tickets suppose there were
n tickets(numbered 1 to n) that were sold out to watch Arjit Singh.So,in order to avoid mis-management due to huge crowd they re-invented a method that they will allow people to enter the arena in pairs.A pair will be selected such as the prime factorizaion of ticket number x and ticket number y has some fators in common 
and the product of common factor of x and y be M.Now a single ticket number x can be selected in  multiple pair.They are interested in only knowing number of
possible pair of enter the arena.They ask for you help as they are very busy in managing other activities of fest.

Your are given a number N denoting number of tickets sold out with each ticket having a distinct number from 1 to n.They also gives you an integer M denoting the product of common factors of any two ticket numbers and ask for how many pairs have such property. 

NOTE:-A particular ticket can be selected in multiple pairs.A number can be selected with him also so (x,x) is a valid pair.
A pair (x,y) is formed iff and only if x ≥ y.

Input Format:-

First line will contain an integer t denoting the number of test cases.
Each of next t lines contains two space integers N and M having usual meaning as described in question.

Output Format:-

For each test case output a single integer denoting the number of possible pair with common factor product as M.

**Constraints:-
1<t ≤ 100

1 ≤ N,M ≤ 1000000** 

SAMPLE INPUT
3
10 2
40 4
20 3

SAMPLE OUTPUT
10
32
12

Explanation

Test Case#1:-

ticket are numbered as 1,2,3,4,5,6,7,8,9,10 and we asked to give number of pair with  product of common factors as  2.The number of pairs are 10 since there are pairs which are

(2,2),(2,4),(2,6),(2,8),(2,10),(4,6),(4,10),(6,8),(6,10),(8,10)

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: