INPUT FILE: prob2.in
OUTPUT FILE: prob2.out
Background
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.
The Problem
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<=109 such that
kn=p.
OUTPUT
For each set of values for n and p output the value of k.
Sample Input File
3 2 16 3 27 7 4357186184021382204544
Output for Sample Input
4 3 1234