def dmod(e,n)
  ( 43 * e + 1 ) % n
end

def gcd(a,b)
  r = a % b
  while r != 0
    a = b
    b = r
    r = a % b
  end
  b
end

a,b = gets.chomp.split(" ").map(&:to_i)

if a < b
  z = a
  a = b
  b = z
end

b = gcd(a,b)
#p b

n = b
i = 1
ans = 1

x = 2
y = 2
visited = [1]

1000.times do
  x = dmod(x,n)
  y = dmod(dmod(y,n),n)
  d = gcd((x-y).abs,n)
  i += 1
  if d == 1
    next
  elsif d < n
    if !visited.include?(d)
      visited << d
      ans += 1
      #p d
    end
  else
    break
  end
end

p ans