Multiplication

On yet another rainy Saturday, Staś could not go outside to play ball, so he stayed home and did what he enjoys most: multiplication.

Starting from $1$, Staś kept multiplying his running product by any natural number of at most five digits that came to mind. To the number obtained this way he finally added $1$, and to his amazement that number $p$ turned out to be prime.

Taking this as a good omen, Staś played on. This time he picked two different natural numbers $a$ and $b$. As before he started from $1$, but now he repeatedly multiplied his running product by the same number $a$, until the remainder of the product modulo $p$ became $b$. Once he finally managed it, Staś fell asleep, worn out by all the multiplying.

How many multiplications did Staś have to perform in this second game?

The first line contains the number of test sets $Z$ ($1 \le Z \le 2$).

The second line contains the prime $p$ that Staś obtained in the way described above ($2 \le p \le 10^{18}$). Because $p - 1$ is a product of natural numbers of at most five digits, every prime factor of $p - 1$ is at most $99999$.

Each of the following $Z$ lines contains two different natural numbers $a$ and $b$ ($1 < a, b < p$).

For each test set, print on its own line the number of multiplications needed so that, starting from $1$ and repeatedly multiplying by $a$, the remainder modulo $p$ becomes $b$. Equivalently, this is the smallest positive integer $k$ with $a^k \equiv b \pmod{p}$. If reaching $b$ is impossible, print $-1$.

In the example above, the prime $p = 13$ arises as follows. Staś first multiplied by $4$ (so he started from $4$), which is not prime. He then multiplied by $3$ to get $12$, and finally adding $1$ gave the prime $13$.

Starting from $1$ and repeatedly multiplying by $12$ yields $12, 1, 12, 1, \dots$, so $9$ never appears. Multiplying by $4$ instead yields $4, 3, 12, 9, 10$ in turn, so $10$ is reached after five multiplications.