n = nil
require 'gmp'
eval File.read('parameter.rb')

a = GMP::Z(3)
require 'prime'
require 'gmp'
m = 1
Prime.each do |p|
  break if p.to_s(2).size > 20
  t = 1
  while t < 2 ** 20
    t *= p
  end
  if p < 100
    while t < 2 ** 1000
      t *= p
    end
  end
  t *= p

  a = GMP::Z(a).powmod(GMP::Z(t), GMP::Z(n))
  if ((a.to_i - 1) % n).gcd(n) % n > 1
    p(['!!', (a.to_i - 1).gcd(n)])
    exit
  end
  p p.to_s(2).size
 end