Invers modular X42716

L’invers modular d’un enter $a$ mòdul $m$ és un enter $x$ tal que:

$$ax \equiv 1 \hspace{10pt} \text{mod } m$$

Donats $a$ i $m$ troba $x$, l’invers modular d’$a$ mòdul $m$ amb $1 \leq x \leq m$. En cas que no existeixi un invers modular indica-ho.

Entrada

L’entrada consisteix en diversos casos, cada cas consta d’una línia, hi ha com a molt $10^5$ línies. Cada línia conté dos enters $a$ i $m$ amb $1 \leq a < m \leq 10^8$.

Sortida

Escriviu un enter per línia: $x$, l’invers modular d’$a$ mòdul $m$ amb $1 \leq x \leq m$. En cas que no existeixi un invers modular escriviu "Sense solucio".

Pista

Planteja el problema en termes d’equacions diofàntiques