HNUMBERS  HNumbers
Note: Some tricky testcases were added on Feb. 26th, 2013 and time limit has been changed. All the solutions have been rejudged and some "Accepted" ones got Wrong 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 to numbers. Recently his friend Matheus Pheverso showed him a group of Hnumbers. Also, his friend told him that, in the Ancient Greek, there Hnumbers 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 Hnumber with N only if: LCM(N, A) = N * A
 LCM is the Lowest Common Multiple between two numbers.
 Example 1: N = 20, Hnumbers = {1, 3, 7, 9, 11, 13, 17, 19}
 Example 2: N = 10, Hnumbers = {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 Hnumbers to create notes. To solve that problem, he needs, for each number N, the number of Hnumbers of N that are between 1 and M, inclusive.
Task
You're given an integer Q  the number of queries. Each query consists of two integer N and M. Your task is to find the number of Hnumbers of N between 1 and 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 are 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 Hnumbers of N less or equal to M.
Sample
Input: 3 20 15 7 3 10 8 Output: 6 3 3
hide comments
Bhuvnesh Jain:
20151222 15:51:26
Please suggest some hints to decrease the time required by solution 

Bhuvnesh Jain:
20151222 15:09:23
AC in one go... 

:.Mohib.::
20150801 21:06:38
Awesome Problem....Really Worth it...!! :)


Altamir Gomes Bispo Junior [UFSCar]:
20140301 04:26:12
@darryl: the problem setter didn't actually determine any specific presentation order for M or/and N. 

nitish rao:
20130914 11:03:34
i'm getting WA :( .. Please look into it. id:10042643 Any corner test cases please?? 

nitish rao:
20130914 11:03:26
Last edit: 20130914 11:03:54 

darryl:
20130903 04:45:37
@problem setter, please check Submission id:9657951. Keep getting WA


!!.Nginx.!!:
20130903 04:45:37
getting WA... any tricky test case please tel.. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130903 04:45:37
@Aditya Pande: That's magic ;) nearly impossible... just find the weakness in test case/constraints :P 

Aditya Pande:
20130903 04:45:37
how can i do better than 0.12s without precomputation... Last edit: 20130102 07:47:13 
Added by:  Mateus Dantas [ UFCG ] 
Date:  20121003 
Time limit:  0.400s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Mateus Dantas 