406075: GYM102254 H High Hopes

In a very distant future, in the last year of graduation at IME, the VFs are coming for César and once again he got low grades. The dream of needing no more than $$$4$$$ to pass the semester is far away, but there is hope, at least for the Encryption discipline.

The professor gave a list of exercises (to raise the VE grade), but this time he got too wicked. To solve the list, César has to decrypt $$$q$$$ messages. The algorithm is quite simple, but there is a hard math part. For every message, César has to find some integer $$$x$$$ such that $$$n^x \equiv 1 \pmod m$$$, where $$$m$$$ and $$$n$$$ are parameters already calculated from the algorithm.

Finishing these calculations is all he need to hand the list. As César needs more than $$$4$$$ on all other disciplines, he doesn't have time to finish it, so you will have to help him.

The first line of input contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of messages to decrypt.

The next $$$q$$$ lines contains, each, two integers, $$${n_i}$$$ and $$${m_i}$$$ ($$$1 \le n_i < m_i \le 10^6$$$) — the parameters $$${n_i}$$$ and $$${m_i}$$$ for the $$$i$$$-th query.

For each $$$n_i$$$ and $$$m_i$$$ from the input, print an integer $$$x_i$$$ ($$$0 \le x_i \le 10^6$$$) such that $$${n_i}^{x_i} \equiv 1 \pmod{m_i}$$$.

If it doesn't exists, print $$$-1$$$.

1
3 5

4

1
2 4

-1