require "prime"

Q = gets.to_i
Queries = Q.times.map{
  gets.split.take(4).map(&:to_i)
}

class Integer
  def f
    return to_enum(:f) unless block_given?
    x = self
    loop{
      yield x
      x = 1 + (x * x + x * 12345) % (10**8+9)
    }
  end
end

Queries.each{|seed, n, k, b|
  factors = b.prime_division
  a = seed.f.take(n+1)
  p factors.map{|f,g|
    z=a.map{|v|
      cnt = 0
      while v % f == 0
        cnt += 1
        v /= f
      end
      cnt
    }.sort[0...k]
    z.sum/g
  }.min
}