This is an interactive problem.

Ocean likes to roll around, because rolling around in the inland sea of Shenzhen Middle School makes you fruitful. As everyone knows, rolling a full circle is equivalent to not rolling at all, so rolling and modulo operations are closely related. Today, Ocean encountered a modulo problem and wants to ask you about it. Ocean has a number $n \le 10^9$, a sequence $c$ that initially only contains the element at position 0, and an interactive library. You do not know $n$ or $c_0$. You can call the following two functions:

• int add(long long x): When this function is called for the $i$-th time, the sequence $c$ adds a new element $c_i := c_{i-1} + x$, and returns $i$. You must ensure $0 \le x \le 10^{18}$. The number of calls to this function cannot exceed $K$. Specifically, if $x = 0$, it will not add a new element and will not count towards the number of calls, but it will still return the index of the last element in the sequence $c$ at that time.
• bool cmp(int i, int j): Returns $[c_i \pmod n < c_j \pmod n]$, that is, if $c_i \pmod n < c_j \pmod n$, it returns 1, otherwise it returns 0. You must ensure that $c_i$ and $c_j$ both exist. This function can be called any number of times within the time limit.

Ocean thinks you cannot find $n$ within $O(\frac{n^{1/4}}{\log n})$ calls to add. Please prove him wrong by getting a zero score.

Interaction

You do not need to, and should not, implement the main function. You need to use #include "ring.h" and implement the function int solve(), which is used to process a set of data and return the answer. In a single run, solve may be called multiple times; please be careful to clear arrays and handle similar issues. Between two calls, the sequence $c$ will be cleared, and the call count for the add function will also be reset to zero.

You can call the add and cmp functions in the format described in the problem statement.

The provided files include an example interactive library ring.h and implementer.cpp. Use g++ ring.cpp implementer.cpp -o ring -std=c++14 -O2 to compile. The input format is: the first line contains the number of test cases; for each test case, one line contains two numbers $n, c_0$. The output should be a meaningful string understandable by humans.

You can use the compilation option -DDEBUG to have the interactive library display the interaction process, or you can modify the interactive library yourself.

Constraints

Let $T$ be the number of test cases in a test point. For all data, it is guaranteed that $10 \le n \le 10^9$, $K \ge 150$, and $T \le 100$.