Remainder Sequence Cycle

Interview

Time limit1sMemory limit128 MB

Summary

Given N and P, simulate the sequence a_{i+1} = a_i*N mod P and output the length of the eventual repeating cycle.

Level: Easy3 of 10
Topics: Simulation, Hash map, Math
Solved: No attempts yet

Problem

Given two natural numbers N and P, define a sequence a_0, a_1, a_2, ... as follows.

a_0 = N
For i >= 0, a_{i+1} is the remainder when a_i * N is divided by P.

If this process continues, a value that has already appeared will appear again, and from then on the same values repeat in the same order. Write a program that finds how many distinct values are contained in the repeating part.

Input

The first line contains the two starting natural numbers N and P, separated by a space.

Output

Print the number of distinct values contained in the repeating part.

Constraints

1 <= N <= 1,000
2 <= P <= 97

Examples2

Example 1
Input
```
67 31
```
Expected output
```
3
```
Example 2
Input
```
96 61
```
Expected output
```
60
```