시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 (추가 시간 없음) 1024 MB1712964.286%

문제

正の整数 M, A が与えられる.整数 x が以下の条件をすべて満たすとき,x は良い整数である.良い整数の個数を求めよ.

  • 1 ≤ x < M.
  • M と x は互いに素.
  • M と A の最大公約数を g とするとき,Ax ≡ g (mod M).

입력

入力は 500 個以下のデータセットからなる.各データセットは次の形式で表される.

M A

各データセットは整数 M と A を含む 1 行からなる.2 ≤ M ≤ 1012 および 1 ≤ A < M を満たすことが保証される.

入力の終わりは 2 つのゼロからなる行で表される.

출력

各データセットに対し,良い整数の個数を 1 行に出力せよ.

예제 입력 1

6 4
5040 128
1000000000000 500000000000
0 0

예제 출력 1

1
8
400000000000