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}$.

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$

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$.