순환소수

문제

$0 < q < P$ 를 만족하는 정수 $q$에 대하여, $\left(\frac{q}{P}\right)$의 $N$진법 소수 표현이 순환소수가 되는 $q$의 개수를 출력하시오.

입력

첫째 줄에 두 정수 $N$과 $P$가 공백으로 구분되어 주어진다. $(2 \le N \le 10^{18}; 2 \le P \le 10^{18})$

출력

조건을 만족하는 $q$의 개수를 출력한다.

예제 1

10 6

출력 1

4

힌트

예를 들어, 16진법의 유한소수 $0.ABC_{16}$을 10진법으로 나타내면 다음과 같다.