discrete logarithm problem

Problem Description

You are given three integers $p, a, b$, where $p$ is a prime number and $p-1$ only has prime factors $2$ and/or $3$. Please find the minimum positive integer $x$ such that $a^x \equiv b \pmod{p}$.

Input

The first line contains an integer $T$ indicating there are $T$ tests. Each test consists of a single line containing three integers: $p, a, b$.

• $T \le 200$
• $65537 \le p \le 10^{18}$
• the prime factors of $p-1$ can only be $2$ or $3$
• $2 \le a, b \le p-1$

Output

For each test, output a line containing an integer $x$, representing the minimum positive value such that $a^x \equiv b \pmod{p}$. If there didn't exist any such number $x$, please output $-1$.

Sample Input

6

65537 2 3

65537 2 4

65537 3 4

65537 4 4

65537 5 4

666334875701477377 2 3

Sample Output

-1

2

45056

1

36864

1957714645490451

Source

2019 Multi-University Training Contest 5