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 A_i & 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 C_i be the count of integers in A having exactly K common one bits with V_i. Then it is required to output the sum of all C_i 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]

---

hide comments

	[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