The Chef has been hunting for a machine developed to change numbers in a rather peculiar manner. This machine has a fixed number cc associated with it and a changing number XX.

## Secret Machine Mania solution codechef

In a single step, the Chef can do the following:

- First, choose any positive integer bb that is a perfect cc-th power of some number (that is, there is some positive integer nn such that b=ncb=nc)
- Then, change X→lcm(b,X)gcd(b,X)X→lcm(b,X)gcd(b,X)

He wants to find the **minimum** number he can change XX into by applying these operations alone **any number of times** (possibly none at all). However, he does not know the exact values of X,cX,c for the machine, but he does have TT guesses for what these values might be. For each of these guesses, compute the minimum number Chef can obtain.

### Input Format

- The first line of input will contain an integer TT, the number of guesses Chef has for the pair (X,c)(X,c). Then the guesses follow.
- Each guess consists of a single line of input containing two space-separated integers X,cX,c.

## Secret Machine Mania solution codechef

For each guess, print on a new line the minimum value that Chef can change XX into by applying any number of operations (possibly none at all).

### Constraints

- 1≤T≤1001≤T≤100
- 1≤X≤10101≤X≤1010
- 1≤c≤301≤c≤30

### Sample Input 1

```
3
1 5
10 1
20 4
```

### Sample Output 1

```
1
1
20
```

### Secret Machine Mania solution codechef

**Guess 11:** It can easily be checked that X=1X=1 cannot be changed.

**Guess 22:** Choose b=101b=101 and change X:10→lcm(10,10)gcd(10,10)=1X:10→lcm(10,10)gcd(10,10)=1. This is the minimum possible value of XX.