在进行了一次质量堪忧的博彩投资后，Bajtazar 决定在附近的赌场赢回损失的钱。他看中了一台提供猜数字游戏的特殊机器。游戏的规则相当不同寻常。

在游戏开始前，机器会以均匀分布随机抽取一个数字 $x$ ($1 \le x \le n$)（即每个数字被抽中的概率相同，均为 $\frac{1}{n}$）。Bajtazar 可以向机器投入一个“bajtalar”（货币单位）并给出一个数字 $y$ ($1 \le y \le n$)。随后，机器会返回 $x$ 和 $y$ 的最大公约数，即 $\gcd(x, y)$。在投入一个 bajtalar 后，除了给出数字 $y$ 之外，Bajtazar 还可以（轻轻）推一下机器，这将导致机器重新随机抽取一个数字 $x$，同样服从均匀分布。你可以假设后续的抽取是相互独立的。

投入一个 bajtalar 后，第三种可能的动作是尝试猜测数字 $x$，这将结束当前游戏（无论猜测是否成功）。如果 Bajtazar 猜对了数字 $x$，他将赢得本局游戏并开始下一局。否则，Bajtazar 将输掉游戏并悲伤地离开赌场，甚至没能领走他可能赢得的奖金。

Bajtazar 知道数字 $n$，并且总共有 $10^7$ 个 bajtalar 可供使用。每一个动作（提问、推机器、尝试猜测）都需要投入一个 bajtalar。请帮助 Bajtazar 在预算耗尽前赢得尽可能多的游戏，且不能输掉任何一局。

交互

这是一道交互题。你需要编写一个程序，使用提供的库与机器进行交互。要使用该库，请在你的程序中包含：

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

该库提供以下函数：

• C++: long long DajN() Python: DajN() 返回题目中的参数 $n$，该值固定为 $10^{18}$。此函数不会影响机器的运行。无需调用它，提供该函数仅为了方便实现。

• C++: long long Pytaj(long long y) Python: Pytaj(y) 返回当前 $x$ 值与 $y$ 的最大公约数 $\gcd(x, y)$。

• C++: void Szturchnij() Python: Szturchnij() 将 $x$ 设置为集合 $\{1, 2, \dots, n\}$ 中的一个随机值（服从均匀分布）。

• C++: void Odpowiedz(long long y) Python: Odpowiedz(y) 如果 $x = y$，则获胜局数增加 1，并立即开始下一局游戏。否则，立即终止程序并判为“答案错误”。

请注意，在使用完 $10^7$ 次查询限制后，程序将自动终止。因其他原因终止程序将导致“答案错误”。换句话说，你的程序必须执行 $10^7$ 次查询才能获得非零分数。

使用任何带有非法参数的函数都将导致“答案错误”。

你的程序不得打开任何文件，也不得使用标准输入和输出。可以使用标准错误输出（stderr），但请记住这会消耗宝贵的时间。禁止故意尝试影响评测库的内部运作。

注意：上述内存限制仅适用于你的解决方案，不包括库所使用的内存。

实验

在 SIO 的“文件与测试”部分，你可以找到 C++ 的 kaslib.h 和 Python 的 kaslib.py 示例文件，它们实现了符合题目要求的库。只需将相应文件放入你的解决方案文件夹中，并使用以下命令之一编译/运行你的解决方案：

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

程序运行后，如果过程顺利，你将收到获胜次数的提示。该库中的随机性始终相同，但可以手动更改，具体说明请参考库中的注释。我们鼓励你阅读这些注释。

样例

样例交互过程

(交互开始 – 机器抽取了 x = 7)
Pytaj(9) -> 1
Szturchnij() -> (机器抽取了新值 x = 6)
Pytaj(2) -> 2
Pytaj(3) -> 3
Odpowiedz(6) -> (我们赢了 – 机器为下一局抽取 x)

评分

你的解决方案在给定测试点上的得分计算如下： 设 $w$ 为获胜局数。则得分为 $\lfloor 100 \cdot \frac{\log_2(1+\min(2000, w))}{\log_2(1+2000)} \rfloor$ 百分比。

本题只有一组测试数据，其中包含 10 个测试点。 机器在单个测试点中抽取的数字序列在每次运行程序时都是相同的。每个测试点的序列均按照题目描述生成。

SIO 中的样例测试 0 与每个正式测试点的结构相同。