require 'prime'

class Integer

  def each_divisor &block
    each_divisor_rec prime_division, 0, 1, &block
  end

  def mod_exp n, m
    b, r = self % m, 1
    while n > 0
      r = r * b % m if n.odd?
      b = b * b % m
      n /= 2
    end
    r
  end

  private

  def each_divisor_rec ps, i, d, &block
    if i == ps.size
      block.call d
    else
      f = 1
      (ps[i][1]+1).times do
        each_divisor_rec ps, i+1, f*d, &block
        f *= ps[i][0]
      end
    end
  end

end

loop do
  xs = gets.split.map(&:to_i)
  break if xs.all?(&:zero?)
  p xs.each_slice(2).map {|a, m|
    ps = Prime.prime_division(m).map(&:first)
    phi = m / ps.reduce(1, :*) * ps.reduce(1) {|r, p| r * (p - 1) }
    phi.enum_for(:each_divisor).sort.find {|d| a.mod_exp(d, m) == 1 }
  }.reduce(1, :lcm)
end