/*
자연수 N P를 주어준다.
처음 출력은 N, 두번째는 N*N%P 세번째는 두번째값*N%P 이런식으로 출력이 된다.
예를 들은 N=67 P=31의 경우
67 25 1 5 25 1 5 이런식으로 출력된다.
이중 25 1 5 는 계속 반복 된다.
이때 반복되는 숫자의 갯수는?

67 31  출력 : 3
9 3 출력 : 1
*/

package ad;

import java.util.ArrayList;
import java.util.Scanner;

public class ad순환순열 {
	static int N,P;
	static ArrayList<Integer> list=new ArrayList<Integer>();

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);

		N=sc.nextInt();
		P=sc.nextInt();

		list.add(N);

		boolean check=true;
		int cnt=0;
		int num=N;

		while(check==true){
			int tmp=(num*N)%P;
			num=tmp;

			if(list.size()>=1){
				for(int i=0; i<list.size(); i++){
					if(tmp==list.get(i)){
						check=false;
						cnt=i;
						System.out.println(list.size()-cnt);
					}
				}
				if(check==true){
					list.add(tmp);
				}
			}
		}
	}
}