50559 - Prime Factors of a Number

Prime factors of a number are the prime number which divides the number evenly and when you multiply all of them you will have the number itself. For example: 12= 2x2x3. 2, 2 and 3 are the prime factors of 12.

Write a program that is going to show k^th prime factor of the given number (m).

Input specification
There is one number n in the first line where 1 ≤ n ≤ 30. Then, in the following n lines, you will be given two numbers m and k where 1 ≤ m ≤ 10⁹ and 1 ≤ k < 15.

Output specification
Show n numbers which represent k^th prime factors of the given numbers.
Note: Prime factors are assumend to be in ascending order. If k is larger than the number of prime factors of the given number, show the biggest prime factor. If the number is prime show the number itself.

Sample Input:
  5
  12 3
  7 1
  20 10
  20001 2
  20000001 3


Sample Output:
  3
  7
  5
  59
  952381


Output Explanation:

• Hence, prime factors of 12 are 2, 2, 3, the result is 3
• 7 is a prime number, the result is 7
• Prime factors of 20 are 2, 2, and 5. Thus, k is larger than the number of factors. The result is 5
• etc.