Count Number Of Rounds

Given an integer ‘N’, you need to make the maximum possible number of moves where each move consists of choosing a positive integer ‘X’ > 1, such that ‘N’ is divisible by ‘X’ and replacing ‘N’ with ‘N/X’.

When ‘N’ becomes equal to 1 and there are no more possible valid moves. You need to stop and your score is equal to the number of moves made.

Given ‘N’ is of the form a! / b! ( i.e. factorial of ‘a’ divided by factorial of ‘b’) for some positive integer ‘a’ and ‘b’ (a ≥ b).

You need to find and return the maximum possible score you can achieve.

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases.      
Then the test cases follow.

The first line of each test case contains 2 space-separated integers ‘a’ and 'b' (defining the value of ‘N’)

Output Format :

For each test case print the maximum integer score achieved.

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= a <= 10^5
1 <= b <= 10^5

Time Limit : 1 sec