E. Seek the Truth
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

Interaction

First, you need to output an integer $$$a$$$ ($$$0\leq a\le 2^n-1$$$) — the initial element you chose for set $$$S$$$.

To make an interaction, output a single line in the following format:

  1. $$$\mathtt{I}\;x$$$ ($$$0\leq x\le 2^n-1$$$) — Insert $$$f(x)$$$ into set $$$S$$$. After that, the jury will return $$$|S|$$$.
  2. $$$\mathtt{Q}\;y$$$ ($$$0\leq y\le 2^n-1$$$) — Query how many $$$z$$$-s in set $$$S$$$ satisfy $$$z \geq y$$$. The jury will return the count of such $$$z$$$-s.

To give the final answer, output a single line in the following format:

  • $$$\mathtt{A}\;k\;c$$$ ($$$1\leq k\le 3$$$, $$$1\leq c\le 2^n-1$$$) — the values of $$$k$$$ and $$$c$$$.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

Note that the grader is non-adaptive. This means that the values of $$$k$$$ and $$$c$$$ are fixed at the beginning and will not change based on your interactions.

Hacks

To hack, use the following format.

The first line should contain a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The only line of each test case should contain three integers $$$n$$$, $$$k$$$, and $$$c$$$ ($$$2 \leq n \leq 60$$$, $$$1\leq k\le 3$$$, $$$1\leq c\le 2^n-1$$$).

The sum of $$$n$$$ over all test cases should not exceed $$$10^5$$$.

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
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:

SolutionJuryExplanation
3There 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.