Note: In this task, you will learn the score of your submissions only after the competition ends.

After a questionable investment in sports betting, Bajtazar decided to recover his lost money in a nearby casino. He took a liking to a specific machine offering a number-guessing game. The rules of the game are quite unusual.

Before the game, the machine draws a number $x$ ($1 \le x \le n$) with a uniform distribution (i.e., the probability of drawing each number is the same and equals $\frac{1}{n}$). Bajtazar can insert one "bajtalar" into the machine and provide a number $y$ ($1 \le y \le n$). The machine then returns the greatest common divisor of $x$ and $y$, i.e., $\gcd(x, y)$. After inserting a bajtalar, instead of providing a number $y$, Bajtazar can also (lightly) nudge the machine, which causes it to draw a new number $x$, also with a uniform distribution. You may assume that consecutive draws are independent of each other.

The third possible action after inserting one bajtalar is to attempt to guess the number $x$, which ends the game (regardless of whether the attempt was successful). If Bajtazar guesses the number $x$, he wins the game and starts a new one. Otherwise, Bajtazar loses and sadly leaves the casino without collecting even his potential winnings.

Bajtazar knows the number $n$ and has $10^7$ bajtalars at his disposal. Each action (asking a question, nudging, attempting to guess) requires inserting one bajtalar. Help Bajtazar win as many games as possible before he runs out of budget, without losing a single game.

Interaction

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

• C++: #include "kaslib.h"
• Python: from kaslib import DajN, Pytaj, Szturchnij, Odpowiedz

The library provides the following functions:

• C++: long long DajN() Python: DajN() Returns the parameter $n$ from the problem statement, which is constant and equal to $10^{18}$. This function does not affect the machine's operation. It does not need to be called and is provided solely for the convenience of implementing solutions.

• C++: long long Pytaj(long long y) Python: Pytaj(y) Returns $\gcd(x, y)$ for the current value of $x$.

• C++: void Szturchnij() Python: Szturchnij() Sets $x$ to a random (uniformly distributed) value from the set $\{1, 2, \dots, n\}$.

• C++: void Odpowiedz(long long y) Python: Odpowiedz(y) If $x = y$, it increases the number of won games by 1 and immediately starts the next game. Otherwise, it immediately terminates execution with a "wrong answer" verdict.

Assume that after using the limit of $10^7$ queries, the program execution will automatically terminate. Terminating the program for any other reason will result in a "wrong answer" verdict. In other words, your program must perform $10^7$ queries to receive a non-zero number of points.

Using any function with incorrect arguments will result in a "wrong answer" verdict.

Your program must not open any files or use standard input and output. It may use standard diagnostic output (stderr), but remember that this consumes precious time. Deliberate attempts to influence the internal operation of the grading library are prohibited.

Note: The memory limit mentioned at the top applies only to your solution and therefore does not include the memory used by the library.

Experiments

In the "Files and tests" section in SIO, you can find sample files kaslib.h in C++ and kaslib.py in Python, which implement a library consistent with the problem statement. Simply place the appropriate file in the folder with your solution and compile/run your solution with the library, e.g., using one of the following commands:

• C++: g++ -O3 -static -o kas kas.cpp -std=c++20
• Python: python3 kas.py

After running the program, if it completes successfully, you will receive a message about the number of wins. The randomness in this library is always the same, but it can be changed manually, as described in the comments within the library. We encourage you to familiarize yourself with it.

Examples

Input 1

(start of interaction – the machine drew x = 7)
Pytaj(9)
Szturchnij()
Pytaj(2)
Pytaj(3)
Odpowiedz(6)

Output 1

1
(machine drew a new value x = 6)
2
3
(we won – the machine draws x for the next game)

Scoring

The number of points your solution receives on a given test is determined as follows. Let $w$ be the number of won games. Then the number of points is $\lfloor 100 \cdot \frac{\log_2(1+\min(2000, w))}{\log_2(1+2000)} \rfloor$ percent of the points assigned to this test.

In this task, there is only one group of tests, which contains exactly 10 tests.

The sequence of numbers drawn by the machine in one test is always the same in every execution of the program on that test. The sequence for each test was drawn as described in the problem.

Example

Test example 0 in SIO has the same structure as each of the individual actual tests.