Time Limit: 1.5 s

Memory Limit: 256.0 MB

Description

Roy and Hridoy play a game on a positive integer X for exactly K moves, alternating turns with Roy first.

• Roy’s move:
  Let p be the smallest prime divisor of the current X.
  Update X = X × p.

• Hridoy’s move:
  Let q be the largest prime divisor of the current X.
  Update X = X ÷ q.

After exactly K moves, output the final value of X.

Note : You may assume that the final value of X after all K moves always fits within the range of a 64-bit signed integer (i.e., ≤ 10¹⁸).

Input

• First line T,(1 ≤ T ≤ 10000) - the number of test case.
• In each test case, Two positive integers X ( 2 ≤ X ≤ \(10^9\) )and K (1 ≤ K ≤ \(10^9\)) ,- current number and the number of moves respectively.

Output

• For each test case, print the final value of X after exactly K moves.

Sample

4
6 2
6 1
10 1
100 5

4
12
20
32

Test case 1: X = 6, K = 2

Initial X = 6

Move 1 (Roy): smallest prime divisor of 6 is 2 → X = 6 × 2 = 12

Move 2 (Hridoy): largest prime divisor of 12 is 3 → X = 12 ÷ 3 = 4

Final value of X = 4.