HNUMBERS - HNumbers

Note: Some tricky test cases 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 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.
  • Example 1: N = 20, H-numbers = {1, 3, 7, 9, 11, 13, 17, 19}
  • Example 2: 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. Each query consists of two integer N and M. Your task is to find the number of H-numbers 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 H-numbers of N less or equal to M.

Sample

Input:
3
20 15
7 3
10 8

Output:
6
3
3

Added by:Mateus Dantas [ UFCG ]
Date:2012-10-03
Time limit:0.400s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Mateus Dantas

hide comments
2013-09-03 04:45:37 Mateus Dantas [ UFCG ]
Thank you guys. So far it's the best problem that I've ever made.
2013-09-03 04:45:37 (Tjandra Satria Gunawan)(曾毅昆)
@Snehasish Roy ;): wow, that's great :-D
2013-09-03 04:45:37 Snehasish Roy ;)
@Tjandra : Now I think we are even. I also did it in 2.6 MB memory and 0.04 sec in c++ !!! :)

Last edit: 2012-12-13 16:07:25
2013-09-03 04:45:37 (Tjandra Satria Gunawan)(曾毅昆)
@Snehasish Roy ;): Congratulations, We're tie in running time, but I still win in memory, I compute the answer without large precomputation that wasted memory...
2013-09-03 04:45:37 Snehasish Roy ;)
Loved doing this :) :)
+1 for the problem setter.
2013-09-03 04:45:37 Mateus Dantas [ UFCG ]
Thank you! :)
2013-09-03 04:45:37 Pranay
nice :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.