H-Numbers 
Note: Some tricky testcases were added on Feb. 26th, 2013 and time limit has been changed. All the solutions have been rejudge and some "Accepted" ones got Wron Answer/Time Limit Exceeded. However, this problem can still be solved by a simple and beautiful solution :)
Ualter is a smart guy, and he loves mathematics and everything related with numbers. Recently his friend Matheus Pheverso showed him a group of H-numbers. Also, his friend told him that, in the Ancient Greek, there h-numbers would be used to create music. This group of numbers can be described in this way:


For 	each integer N, a positive integer  A is H-Number with N only if:
 - LCM(N,A) = N*A


LCM 	is the Lowest Common Multiple between two numbers.


Ex1: 	N = 20, H-Numbers = {1,3,7,9,11,13,17,19}


Ex2: 	N = 10, H-Numbers = {1,3,7,9}


 
Ualter loves classical music mainly Pachelbel's compositions. In order to achieve his old dream, he's willing to make a version of Canon in D using only h-numbers to create notes. To solve that problem, he needs, for each number N, the number of h-numbers of N that are between 1 and M, inclusive.
Task
You're given an integer Q - the number of queries - , and two numbers N,M in each query, your task is to find the number of h-numbers of N between 1 and an integer M.
Input
In the first line there's an integer Q ( 1 <= Q <= 10^5 ) representing the number of queries. In the next Q lines there're two numbers N,M ( 1 <= N, M <= 10^5 ,  M < N ). 
Output
You have to print for each query an integer xi representing the number of H-numbers of N less  or equal to M.
Examples
 

 



Input:
3
20 15
7 3
10 8
 




Output:
6
3
3