CF2222E Seek the Truth

[Nanatsukaze - Connect the World](https://www.youtube.com/watch?v=M-IayQIR0XA) This is an interactive problem. There are two hidden integers $ k $ and $ c $ such that $ k\in \{1,2,3\} $ and $ 1\le c\le 2^n-1 $ . Note that $ c\neq 0 $ . Before any interaction, you need to tell the jury a non-negative integer $ a\le 2^n-1 $ . The grader will then use $ a $ as the initial element in the set $ S $ , that is, initially $ S = \{a\} $ . Next, you can make at most $ n+3 $ queries of the following two types: 1. Select an integer $ x $ such that $ 0\leq x\le 2^n-1 $ . The jury will insert $ f(x) $ into $ S $ and then respond with $ |S| $ (i. e., the size of $ S $ after the insertion); 2. Select an integer $ y $ such that $ 0\leq y\le 2^n-1 $ . The jury will respond with the number of integers $ z $ such that $ z\in S $ and $ z\geq y $ . The definition of $ f(x) $ is as follows: $$$ f(x)= \begin{cases} x\,\&\,c & \text{if}\, k=1,\\ x\,|\,c & \text{if}\, k=2,\\ x\oplus c & \text{if}\, k=3.\\ \end{cases} $$$ Here, $ \& $ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND), $ | $ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR), and $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Your task is to determine the values of $ k $ and $ c $ using at most $ n+3 $ interactions. Please note that reporting the answer does not count towards the $ n+3 $ interactions.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \leq n \leq 60 $ ). Then, interaction follows. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

N/A

Below is the interaction process in the example: SolutionJuryExplanation3There are $ 3 $ test cases.2 $ n=2 $ . The hidden integer values are $ k=1 $ and $ c=3 $ .3Initially, $ S = \{3\} $ .I 31Insert $ f(3)=3\,\& \,3=3 $ into $ S $ . Then $ S=\{3\} $ , so the response is $ |S|=1 $ . Note that elements in set $ S $ are not allowed to be repeated.A 1 3The solution concludes that $ k=1 $ and $ c=3 $ .2 $ n=2 $ . The hidden integer values are $ k=2 $ and $ c=2 $ .1Initially, $ S = \{1\} $ .I 02Insert $ f(0)=0\,|\,2=2 $ into $ S $ . Then $ S=\{1,2\} $ , so the response is $ |S|=2 $ .Q 21When $ z $ is $ 2 $ , it satisfies $ z\in S $ and $ z\geq 2 $ , so the response is $ 1 $ .Q 12When $ z $ is $ 1 $ or $ 2 $ , it satisfies $ z\in S $ and $ z\geq 1 $ , so the response is $ 2 $ .Q 02When $ z $ is $ 1 $ or $ 2 $ , it satisfies $ z\in S $ and $ z\geq 0 $ , so the response is $ 2 $ .I 33Insert $ f(3)=3\,|\,2=3 $ into $ S $ . Then $ S=\{1,2,3\} $ , so the response is $ |S|=3 $ .A 2 2The solution concludes that $ k=2 $ and $ c=2 $ .2 $ n=2 $ . The hidden integer values are $ k=3 $ and $ c=1 $ .1Initially, $ S = \{1\} $ .I 12Insert $ f(1)=1\oplus 1=0 $ into $ S $ . Then $ S=\{0,1\} $ , so the response is $ |S|=2 $ .I 02Insert $ f(1)=0\oplus 1=1 $ into $ S $ . Then $ S=\{0,1\} $ , so the response is $ |S|=2 $ . Note that elements in set $ S $ are not allowed to be repeated.A 3 1The solution concludes that $ k=3 $ and $ c=1 $ .Empty lines in the example input and output are given only for better readability; you don't need to output them in your solution. Note that in the example, the given queries are in fact insufficient to uniquely determine the values; they are given only to illustrate the input/output format.