Remainder Sequence Cycle

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.

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

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

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