First, consider the case where all queries have the same value of \(C\).

Let \(d[A][x][B]\) hold the following four pieces of information: “among the integers in \([0,2^A)\) whose remainder when divided by \(C\) is \(x\), how many consecutive integers with popcount at least \(B\) appear at the beginning, how many at the end, how many in the longest consecutive run in the interior, and whether all of them have popcount at least \(B\).” The number of states of \(d\) is \(O(CK\log NK)\), and the DP transitions can be computed in \(O(1)\) per state by processing in increasing order of \(A\).

We then consider computing the answer using this \(d\).

First, fix the remainder \(x\) when \(X\) is divided by \(C\).

Let \(\text{INF}\) be a constant such that the answer to the problem is less than \(2^{\text{INF}}\).

The answer to the problem lies in \([0,2^{\text{INF}})\).

We consider whether it falls in \([0,2^{\text{INF}-1})\) or \([2^{\text{INF}-1},2^{\text{INF}})\). The values \(X,X+C,\ldots,X+(N-1)C\) fall into one of the following three patterns:

• All of \(X,X+C,\ldots,X+(N-1)C\) lie in \([0,2^{\text{INF}-1})\).
• \(X,X+C,\ldots,X+(N-1)C\) straddle \(2^{\text{INF}-1}\), that is, they are partially in both \([0,2^{\text{INF}-1})\) and \([2^{\text{INF}-1},2^{\text{INF}})\).
• All of \(X,X+C,\ldots,X+(N-1)C\) lie in \([2^{\text{INF}-1},2^{\text{INF}})\).

Which of the three patterns applies can be easily determined from the information in \(d[\text{INF}-1][*][*]\).

Then, by recursively applying the same procedure to the narrowed interval, we can find the answer.

By precomputing \(d\) for each \(C\), each test case can be solved in \(O(\text{INF}\times C)\).