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