Index Equation 2

Problem Description

Answer $T$ queries. Each query gives a number $a, b, m$; output the smallest non-negative integer $x$ satisfying $a^x \equiv b \pmod {m}$.

Input Format

The first line contains one integer $T$. The following $T$ lines each contain three integers $a, b, m$.

Output Format

One integer: the smallest non-negative integer solution; if there is no solution, output -1.

Sample Input

3
2 0 1024
123 456 789
114514 1919810 504289861

Sample Output

10
49
2

Constraints

For all data, it is guaranteed that $T\leq 100$, $1\leq a < m \leq 10^9$, $0\leq b < m \leq 10^9$.

Hint

• This asks for the discrete logarithm. Use the Baby-step Giant-step (BSGS) algorithm, accounting for the case $b=0$ (a solution exists iff $a$ is not coprime to $m$ in a way that eventually yields 0, or simply check small $x$ first) and extend it to the general (non-coprime) case with the extended BSGS method.