This problem is a programming version of Problem 124 from projecteuler.net
The radical of , , is the product of the distinct prime factors of . For example, , so .
If we calculate for , then sort them on , and sorting on if the radical values are equal, we get:
Let be the th element in the sorted column; for example, and .
Given and , if is sorted for , find .
Input Format
The first line of input contains , the number of test cases.
Each test case consists of a single line containing two integers, and .
Constraints
For the first few test files worth 30% of the total points:
For the next few test files worth 30% of the total points:
For the last few test files worth 40% of the total points:
Output Format
For each test case, output a single line containing a single integer, the requested value .
Sample Input
3
10 4
10 6
12 9
Sample Output
8
9
12
Explanation
The first two cases can be answered by consulting the table in the problem statement. For the third test case, so the new table is:
In this case, is now .