CF1027G X-mouse in the Campus

The campus has $ m $ rooms numbered from $ 0 $ to $ m - 1 $ . Also the $ x $ -mouse lives in the campus. The $ x $ -mouse is not just a mouse: each second $ x $ -mouse moves from room $ i $ to the room $ i \cdot x \mod{m} $ (in fact, it teleports from one room to another since it doesn't visit any intermediate room). Starting position of the $ x $ -mouse is unknown. You are responsible to catch the $ x $ -mouse in the campus, so you are guessing about minimum possible number of traps (one trap in one room) you need to place. You are sure that if the $ x $ -mouse enters a trapped room, it immediately gets caught. And the only observation you made is $ \text{GCD} (x, m) = 1 $ .

The only line contains two integers $ m $ and $ x $ ( $ 2 \le m \le 10^{14} $ , $ 1 \le x < m $ , $ \text{GCD} (x, m) = 1 $ ) — the number of rooms and the parameter of $ x $ -mouse.

Print the only integer — minimum number of traps you need to install to catch the $ x $ -mouse.

In the first example you can, for example, put traps in rooms $ 0 $ , $ 2 $ , $ 3 $ . If the $ x $ -mouse starts in one of this rooms it will be caught immediately. If $ x $ -mouse starts in the $ 1 $ -st rooms then it will move to the room $ 3 $ , where it will be caught. In the second example you can put one trap in room $ 0 $ and one trap in any other room since $ x $ -mouse will visit all rooms $ 1..m-1 $ if it will start in any of these rooms.