We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #124: Ordered radicals

Project Euler #124: Ordered radicals

Problem
Submissions
Leaderboard
Discussions

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 .

Author

kevinsogo

Difficulty

Advanced

Max Score

100

Submitted By

264

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy