Project Euler #124: Ordered radicals

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

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 .