MCPC06G - Root of the Problem

Given positive integers B and N, find an integer A such that A^N is as close as possible to B. (The result A is an approximation to the Nth root of B.) Note that A^N may be less than, equal to, or greater than B.

Input

The input consists of one or more pairs of values for B and N. Each pair appears on a single line, delimited by a single space. A line specifying the value zero for both B and N marks the end of the input. The value of B will be in the range 1 to 1,000,000 (inclusive), and the value of N will be in the range 1 to 9 (inclusive).

Output

For each pair B and N in the input, output A as defined above on a line by itself.

Example

Input:
4 3
5 3
27 3
750 5
1000 5
2000 5
3000 5
1000000 5
0 0 Output: 1
2
3
4
4
4
5
16

Added by:Tamer
Date:2009-11-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:ACM Mid-Central Regional Programming Contest 2006

hide comments
2009-11-16 15:32:57 numerix
Should be moved to tutorial section ... -> it's done.

Last edit: 2009-11-16 16:00:44
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.