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 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