The first observation is that for a fixed set of species, the max. number of farms is the GCD of their a_i (we can say c_j=a_{N+j}). So we want the sum of GCDs over all K-element subsets.

The second observation is that this sum for the first x+1 species = sum for the first x species + number of K-1-element subsets containing the x-th species. In order to recalculate it, we only need to find out the number of K-1-element subsets such that their numbers and a_x have GCD equal to g for each divisors g of a_x (obviously, that GCD can't be a non-divisor of a_x); let's call the number of such subsets for given x p(g), then the answer in step x+1 = answer in step x + sum gp(g).

It's much easier to calculate the number of K-1-element subsets whose GCD is a multiple of g; let's call that number P(g). We'll get to that later, it's more important to show how to get p-s from P-s.

We'll calculate p-s in the order of decreasing g. At first, let's take p(g)=P(g); we need to subtract the subsets whose GCD is strictly bigger than g and a multiple of g. Since we calculated p(g') for all g' > g already, we can just subtract all p(g') such that g' > g is a multiple of g. However, we need to list divisors for all numbers anyway, so it's simpler to subtract p(g') from all p-s of proper divisors of g' right after calculating it.

The time complexity of this is O(number of pairs g | g' | a_x). The maximum number of such pairs can be found easily if we know divisor lists; it's 8505 for a_x <= 10^6. We don't need any modulos there, so that's manageable.

Now to computing P(g). If there are M_g species with numbers divisible by g, then P(g)={M_g over K-1}. Since M <= N+Q, we can precompute factorials and their modular inverses, which allows us to compute P(g) in O(1) time.

Computing M_g is very similar to p-s from P-s: when the number of species with f flowers (an analogy of P) increases by 1, M_d for all d|f (which is an analogy of p) increases by 1.

We also need divisor lists; for them, we can use a simplified sieve of Erathostenes. There are O(Alog{A}) divisors, where A=10^6 and the maximum number of divisors of one number <= A is D ~ 300, which means the total time complexity is O((N+Q)(D+8500)+Alog{A}), where the constant next to D is larger than the one next to 8500 due to modulos and more stuff to compute.

This may be too slow; to speed it up, we can use the fact that we don't need online processing for the first N added flowers.