ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1456. Jedi Riddle 2

Time limit: 0.25 second
Memory limit: 64 MB


Everyone wants to be respected and famous. At that many of us forget that most people became respected and famous after death only. For instance, let us take system administrator Vasily "Jedi Master" Slipman. For the first time his name was mentioned in connection with the sensational case concerning password decoding. That time nearly a half of the humanity strived for getting access to an archive, which contained some information of great pith and moment (this story is fully described in the problem "Jedi riddle").
After that case, the greatest cryptography scientists became interested in uncommon personality of Mr. Slipman and his research activities. In-depth study of Vasily's scientific heritage revealed, that during the last years of his life he was trying to understand the nature of the Force itself. Mr. Slipman tried to find the legendary Number of Force. In the volume XII of "The Book of the Light and the Darkness" an amazing experiment is described in detail:


"...And I took the Number of Light A and the Number of Darkness N. However the Darkness and the Light cannot be disjointed, so I took the One since Its essence is unknowable and sacred. And then I multiplied the One by the Number of Light, divided the result by the Number of Darkness and took the Remainder Z[1] = (1*A) modulo N. Then I multiplied the Remainder by the Number of Light, divided the result by the Number of Darkness and took the Remainder Z[2] = (Z[1]*A) modulo N once more. Being impatient, I was multiplying, dividing and taking the new Remainders Z[i] again and again... Until the day came when I understood I had been blind. The One is a key to the Force, the Alpha and the Omega, the Beginning and the Ending. I returned to my work with the eagerness I had never felt before. Because I knew - the Number of Force X will be found as soon as some Remainder Z[X] is equal to the One. And may the Force be with me..."


The only line contains the integer Numbers A and N (2 ≤ A < N ≤ 109).


You should output the minimal positive Number X, if it exists. Otherwise you should output zero.


7 20


In the sample, the Remainders Z[1] = (1*7) modulo 20 = 7, Z[2] = (7*7) modulo 20 = 9, Z[3] = (9*7) modulo 20 = 3 and Z[4] = (3*7) modulo 20 = 1.
Problem Author: Ilya Grebnov, Dmitry Kovalioff, Nikita Rybak
Problem Source: Timus Top Coders: Second Challenge