2. Power of Cryptography

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=kⁿ 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<=10¹⁰¹ and there exists an integer k, 1<=k<=10⁹ such that

kⁿ=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