1997 Woburn Computer Programming Challenge

2. Power of Cryptography

Current work in cryptography involves (among other things) computing large prime numbers and computing powers of numbers modulo these large primes. Work in this area has resulted in the practical use of result from number theory and other branches of mathematics once considered to be only of theoretical interest. This problem involves the efficient calculation of integer roots of numbers.

Given an integer n ≥ 1 and an integer p ≥ 1 you are to write a program that determines the nth root of p — it is guaranteed that p is the nth power of some integer k, i.e. p=kn for some integer k; this is the integer you are to find.

Input

The first line of the input is M, the number of test cases to consider.
The input consists of M pairs of numbers n and p with each number on a line by itself. For all of these pairs, 1 ≤ n ≤ 200, 1 ≤ p ≤ 10101 and there exists an integer k, 1 ≤ k ≤ 10101 such that

kn=p.

Output

For each set of values for n and p output the value of k.

Sample Input

3
2
16
3
27
7
4357186184021382204544

Sample Output

4
3
1234

All Submissions
Best Solutions


Point Value: 20
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 28, 2008

Languages Allowed:
C++03, PAS, C, ASM, C#, C++11

Comments (Search)

What a monster problem programming BigInts for the first time is.... So many tiny bugs... :P

At least one gains programming stamina from overexertion...

Whatever happened to that?

Did you bother to READ?
All but one (or was it two) of the test cases require essentially no effort to solve. Just giving partial points for them would be too much.


There is no "easy" way to do this.
You have to find a way to multiply numbers of any length.
Try doing "A plus B 2" first.


Yes, it's called exp, and computes the exponential of its argument, that is, exp(x) = ex. However, using logs/antilogs no longer works for this problem...

So close to getting 15 points...
Can you make it 15 partial points instead??

No, it would be too easy then.
The answer for the last case won't fit in real or even extended.

This problem used to be solvable using a long double to store p, since you only need a handful of digits, so a new test case has been added, with 1 <= k <= 10101.