The jury has chosen a certain integer $x$ from the interval $[1, n]$. Your task is to guess it. To avoid having to do this completely blindly, you can make queries. In each query, you can provide an integer $y$ from the interval $[0, c]$, and in response, we will reveal the number of divisors of the number $x + y$.

To make the task slightly more difficult, you will have to solve $t$ test cases during a single program execution. The total number of queries you can make across all of them is limited by $q$.

Interaction

This is an interactive task. You must write a program that communicates with the jury using the provided library. To use the library, you must include the following in your program:

• C++: #include "dzilib.h"
• Python: from dzilib import GetT, GetN, GetQ, GetC, Ask, Answer

The library provides the following functions:

• GetT() – Returns the parameter $t$ – the number of test cases to solve.
• GetN() – Returns the parameter $n$ – the upper bound on the hidden values $x$.
• GetQ() – Returns the parameter $q$ – the limit on the total number of queries you can make across all $t$ test cases.
• GetC() – Returns the parameter $c$ – the limit on the values $y$ you provide.
• Ask(y) – Returns the number of positive divisors of the hidden number $x$ increased by $y$. You must satisfy $0 \le y \le c$.
• Answer(z) – Informs the library that, in your opinion, the hidden value $x$ is $z$. It returns nothing (in C++, the function is of type void).

In Python, all library function parameters and return values are of integer type. In C++, the types accepted and returned by the functions are the same as in the provided example library, which is described further in the Experiments section.

At any moment during the program's execution (except at its very end), one test case will be active. The first test case is activated immediately after the program starts. When a test case is active, you can make queries using the Ask function. When you decide that you know the hidden value $x$, you can provide it using the Answer function, and the library will verify it. If the provided value is incorrect, the library will terminate the program with a "wrong answer" verdict. If the value is correct, the function will finish; if the solved test case was not the last one, the next one will be activated immediately. After providing the answer for the last test case, you should terminate the program. If you do not do this and attempt to use the Ask or Answer function, you will receive a "wrong answer" verdict.

You can use the GetT, GetN, GetQ, and GetC functions at any time during the program's execution, and the values returned by them will not change. These functions do not count towards the query limit, but they do consume CPU time. The value $q$ only limits the number of calls to the Ask function. The moment you exceed the total allowed number of queries, the library will terminate the program, and you will receive a "wrong answer" verdict.

Do not read any data from standard input or write anything to standard output. Deliberate attempts to influence the internal operation of the grading library are prohibited.

The hidden values $x$ in all tests and their order are determined in advance. This means that the library your program communicates with will not be malicious and will not adapt its behavior to your program's actions.

The limits given in the problem statement apply only to the time and memory used by your program. The library's execution time and memory usage may depend on the test and the exact behavior of your program. For this reason, the time and memory limits in SIO2 are slightly higher than those stated in the problem.

Examples

Input 1

2
1000000
10000
1000000000000000
1000
1

Output 1

Ask(1)
8
Ask(24)
11
Answer(1000)
Answer(1)

Note

In the example test, $t = 2$, $n = 10^6$, $q = 10^4$, $c = 10^{15}$, the hidden values are $1000$ and $1$ respectively. Two Ask queries were made, which is within the $10\,000$ query limit. Remember that the total number of queries for all test cases in one test is counted.

Evaluation

Within a group of tests, all tests have the same values of $t$, $n$, $q$, and $c$, which are presented in the table below:

The example test does not belong to any group. You can solve it, but note that it is possible to get full points without solving it.

Experiments

Example incorrect solutions and example libraries in C++ and Python can be found in the archives in the Files section on SIO2. These solutions and libraries illustrate the types returned and accepted by all functions. Example libraries may differ in behavior from the one that will be used to evaluate the solutions and may not meet the problem's assumptions. They are only intended to show how to interact with the program.

A C++ solution dzi.cpp can be compiled as follows:

g++ -O3 -static -o dzi dzi.cpp dzilib.cpp -std=c++20

Ensure that the files dzilib.h and dzilib.cpp are in the same folder as the solution.

A Python solution dzi.py can be run with the command:

python dzi.py

Ensure that the file dzilib.py is in the same folder as the solution.

After starting, at the very beginning of the program's execution, the library receives the values $t$, $n$, $q$, and $c$ sequentially on standard input, followed by the subsequent hidden values $x$. The input file corresponding to the example test is located in both archives under the name dzi0.in.