### Y sequence

Time Limit: 1000 ms
Memory Limit: 65536 KiB

#### Problem Description

Yellowstar likes integers so much that he listed all positive integers in ascending order,but he hates those numbers which can be written as a^b (a, b are positive integers,2<=b<=r),so he removed them all.Yellowstar calls the sequence that formed by the rest integers“Y sequence”.When r=3,The first few items of it are：

2,3,5,6,7,10......

Given positive integers n and r，you should output Y(n)(the n-th number of Y sequence.It is obvious that Y(1)=2 whatever r is).

2,3,5,6,7,10......

Given positive integers n and r，you should output Y(n)(the n-th number of Y sequence.It is obvious that Y(1)=2 whatever r is).

#### Input

The first line of the input contains a single number T:the number of test cases.

Then T cases follow, each contains two positive integer n and r described above.

n<=2*10^18,2<=r<=62,T<=30000.

Then T cases follow, each contains two positive integer n and r described above.

n<=2*10^18,2<=r<=62,T<=30000.

#### Output

For each case,output Y(n).

#### Sample Input

2 10 2 10 3

#### Sample Output

13 14

#### Hint

#### Source

2015 Multi-University Training Contest 1