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

6
65537 2 3
65537 2 4
65537 3 4
65537 4 4
65537 5 4
666334875701477377 2 3

-1
2
45056
1
36864
1957714645490451