Number

2

2 votes
Hard
Problem

I give you a number P. When you divide this number with one of its factor you get 1 chocolate. Number is then replaced with the quotient. You stop when the number becomes 1.

Number P is of the form A!/B!

Find the maximum possible chocolates that you can get.

 

INPUT

First line contains the integer T, denoting number of test cases.

Next T line contains 2 integers, A and B.

 

OUTPUT

Output single integer, maximum possible chocolates.

 

CONSTRAINTS

1<=T<=106

0<=B<=A<=5*106

Sample Input
2
3 1
6 3
Sample Output
2
5
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?