Root

Interview

Time limit1sMemory limit128 MB

Summary

For each pair B and N, find the positive integer A that makes A^N as close to B as possible.

Level: Medium4 of 10
Topics: Binary search, Math, Brute force, Implementation
Solved: No attempts yet

Problem

Given positive integers $B$ and $N$ , write a program that finds the positive integer $A$ whose $A^N$ is closest to $B$ . In other words, output the $A$ that minimizes $|A^N - B|$ . Note that $A^N$ may be less than, equal to, or greater than $B$ .

Input

The input consists of several test cases. Each test case is a single line containing two integers $B$ and $N$ separated by a space. ( $1 \le B \le 1{,}000{,}000$ , $1 \le N \le 9$ )

The last line of the input contains two zeros; this line is not processed.

Output

For each test case, output the corresponding $A$ on its own line.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
50 2
0 0
```
Expected output
```
7
```