## ANDQQ - AND Queries

Given an array A of N integers, you are required to solve Q queries. Each query consists of a positive integer V and a non-negative integer K. For each query, find out how many numbers in the array A have exactly K common one bits with the number V.

In other words, for each query, you need to calculate how many numbers are there in the array such that Ai & V have exactly K bits set in its binary representation, where & denotes the bitwise AND operation.

Note that since the input can be huge, they will be generated randomly using a pseudorandom generator, whose parameters will be given as input. Also for similar reasons, it is not required to output the result for every query, rather compute the sum of this value for all queries and output this sum. More specifically, for the i-th query, let Ci be the count of integers in A having exactly K common one bits with Vi. Then it is required to output the sum of all Ci only.

### Input

The first line contains an integer T, denoting the number of test cases. Each test case contains six space separated integers in the order: seed, N, Q, mod_A, mod_V, mod_K. Afterwards, the input for each test case will be generated as described by the python code below.

```def random():
global seed
seed = (seed * 997 + 29) % 2117566807
return seed

A = [0 for _ in range(N)]

for i in range(N):
A[i] = random() % mod_A

V = [0 for _ in range(Q)]
K = [0 for _ in range(Q)]

for i in range(Q):
V[i] = random() % mod_V
K[i] = random() % mod_K
```

Note that the seed is a global variable which gets updated after each random call, with the initial value being given as input.

### Constraints

• 1 ≤ T ≤ 25
• 1 ≤ N, Q ≤ 250000
• 0 ≤ seed < 2117566807
• 1 ≤ mod_A, mod_V ≤ 250000
• 1 ≤ mod_K ≤ 19
• ### Output

For each test case, output the case number followed by the required output. Please refer to the sample input/output section for more clarity of the format.

### Sample Input

```2
1 10 10 4 4 3
0 100 1000 10000 100000 10

```

### Sample Output

```Case 1: 26
Case 2: 10260

```

### Explanation

For the first case:

A = [2, 3, 0, 1, 1, 2, 2, 3, 1, 0]

V = [2, 0, 3, 1, 0, 0, 2, 0, 0, 1]

K = [0, 2, 1, 1, 1, 2, 2, 0, 2, 2]

C = [5, 0, 6, 5, 0, 0, 0, 10, 0, 0] [Rampage] Blue.Mary: 2020-02-25 17:28:38 I think my AC program doesn't use FWT at all. BTW, the first line of current sample is superfluous. -> Thanks, copy paste mistake. Fixed now. It can be also be solved DP on subsets. I wanted to add those tags as well but for some reason I can't. Last edit: 2020-02-25 19:13:35