CF2222E.Seek the Truth

Nanatsukaze - Connect the World

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, $ | $ denotes the bitwise OR operation, and $ \oplus $ denotes the bitwise XOR operation.

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 $ .

null

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.