Limits 2s, 32 MB

Uban and Aliban are 2nd2^{nd} year undergraduate students. Uban is a newbie sport programmer, whereas Aliban is blue. Recently they came to know about FatGpt. FatGpt is a chatbot software that simulates human-like conversations with users via chat. Its essential task is to answer user questions with instant messages. After hearing about Chatbot AI, Uban, and Aliban argue that AI can solve any problem. Uban thinks AI can replace humans, whereas Aliban says AI can only solve easy to medium-level tasks and can't solve critical thinking tasks. Their argument finished without any final statement.

After a few days back, Aliban finds an interesting problem in an online judge, which needs complex thinking to solve. Aliban comes to Uban and says, "I find an interesting problem, and I can solve this. Let's challenge FatGpt, and I am sure it will prove you wrong that AI can replace humans."

Uban tells FatGpt about the problem statement and asks to write a C++ solution. The conversation between Uban and FatGpt is given below:

Uban's Question: "You are given an array AA of length NN. You have to process QQ queries. A single integer XX represents each query. In each query, you have to find the number of unique pairs such thatAi&Aj=XA_i \:\&\: A_j = X . Here, &\& means bitwise and operator.”

FatGpt's Response:

After getting FatGpt's response, Uban became excited and started yelling at Aliban, “You See….”. Aliban says, "Let's submit it and make you surprised." After submitting FatGpt's solution, they got “Wrong Answer”.

Now your task is to write the correct solution to this problem. The definition of the unique pairs can be found in the note section.


The first line contains a positive number TT (1T10)(1 \le T \le 10) — the number of test cases. The following is a description of the test cases.

The first line of the description of each test case contains two positive numbers NN (1N2105)(1 \le N \le 2*10^{5}) and QQ (1Q105)(1 \le Q \le 10^{5}) — the size of the array and the number of queries.

The second line of the description of each test case contains NN integers A1,A2,,ANA_1,A_2,…,A_N (0Ai106)(0 \le A_i \le 10^{6}) — the elements of array AA.

Then QQ lines follow; each line contains a number XX (0X106)(0 \le X \le 10^{6}), giving the queries.


For each test case, print “Case tctc:”, where tctc means the number of the test case. After that, for each query, print the number of unique pairs. See the sample test case for a better understanding of the output format.


7 3
78 1 34 33 1 14 89
9 4
1 2 3 4 5 6 7 8 9
Case 1:
Case 2:

Unique pairs: Let's say an array has elements [1, 2, 4, 5, 1]. Then there will be 77 unique pairs - (1,2),(1,4),(1,5),(1,1),(2,4),(2,5),(4,5)(1,2), (1,4), (1,5), (1,1), (2,4), (2,5), (4,5). (1,2)(1,2) and (2,1)(2,1)is considered same.


Login to submit.


62% Solution Ratio
pathanEarliest, 4M ago
pathanFastest, 0.6s
RakibJoyLightest, 5.8 MB
nh_nayeemShortest, 1304B
Toph uses cookies. By continuing you agree to our Cookie Policy.