Modular Self Exponentiation Equation

Given two integers n and D where D and n are coprime, find an integer x (0 ≤ x ≤ 2¹²⁵) such that

$$x^x \equiv D \pmod{n}$$

It is guaranteed that the largest prime factor of n does not exceed $$10^5$$. If there is no solution within the range, output -1; if multiple solutions exist, output any one of them.

The input contains multiple test cases.

inputFormat

The first line contains an integer T (the number of test cases). Each of the next T lines contains two integers n and D.

outputFormat

For each test case, output one integer x (0 ≤ x ≤ 2¹²⁵) satisfying the equation. Output -1 if no such x exists.

sample

1
5 1

1