WC '97 P2 - Power of Cryptography

View as PDF

Submit solution

Points: 20
Time limit: 1.0s
Memory limit: 16M

Problem type
Allowed languages
Assembly, Brain****, C, C++, COBOL, Forth, Fortran, Java, Lua, Prolog, Text, Turing
1997 Woburn Computer Programming Challenge

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 \ge 1n \ge 1 and an integer p \ge 1p \ge 1 you are to write a program that determines the nn-th root of pp — it is guaranteed that pp is the nn-th power of some integer kk, i.e. p=k^np=k^n for some integer kk; this is the integer you are to find.

Input Specification

The first line of the input is MM, the number of test cases to consider.
The input consists of MM pairs of numbers nn and pp with each number on a line by itself. For all of these pairs, 1 \le n \le 200, 1 \le p \le 10^{101}1 \le n \le 200, 1 \le p \le 10^{101} and there exists an integer kk, 1 \le k \le 10^{101}1 \le k \le 10^{101} such that k^n=pk^n=p.

Output Specification

For each set of values for nn and pp output the value of kk.

Sample Input


Sample Output



There are no comments at the moment.