Statement : E. 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:
- 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);
- 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$.
Input
3
2
1
2
2
1
2
2
3
2
2
2
2
Output
3
I 3
A 1 3
1
I 0
Q 2
Q 1
Q 0
I 3
A 2 2
1
I 1
I 0
A 3 1
Note
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.