- All Contests
- ProjectEuler+
- Project Euler #124: Ordered radicals

# Project Euler #124: Ordered radicals

# 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**

```
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 .