CF2174E1.Game of Scientists (Version 1)

The two versions have different constraints on $k$, $c$. Solving one of the two versions does not necessarily solve the other. You may want to read both versions. Hacks are disabled in both versions.

This is an interactive problem.

During the time of the Ottoman Empire, many scientists were at work. You decided to study their daily life and stumbled upon an interesting game that was popular at that time. One scientist would think of an integer $x$, such that $1 \leq x \leq c$. Another scientist would try to guess it. He could specify the base of the numeral system $2 \leq b \leq c$ and would receive as a response the sum of the digits of the number $x$ in base $b$, if $x \geq b$, or $-1$ if $x \lt b$.

You wrote a program that can think of a number $x$ and respond to the question. Now you want to play with it and learn to guess using $\leq k$ queries.

两个版本对 $k$、$c$ 的约束条件不同。解决其中任一版本并不必然意味着解决了另一版本。建议您阅读两个版本。两个版本均禁用 Hack。

这是一个交互式问题。

在奥斯曼帝国时期，许多科学家都在从事研究工作。您决定研究他们的日常生活，并偶然发现了一款当时广为流行的游戏。一名科学家会想出一个整数 $x$，满足 $1 \leq x \leq c$；另一名科学家则尝试猜出该数。他可以指定一个进制 $b$（满足 $2 \leq b \leq c$），并收到如下响应：若 $x \geq b$，则返回 $x$ 在 $b$ 进制下的各位数字之和；若 $x \lt b$，则返回 $-1$。

您编写了一个程序，该程序能随机选定一个数 $x$ 并对查询作出响应。现在您希望与该程序进行游戏，并学会仅用 $\leq k$ 次查询就猜出 $x$。

The first line contains three integers $t$, $k$, $c$ ($1 \leq t \leq 10^4$, $\mathbf{k = 4}$, $\mathbf{c = 4 \cdot 10^{18}}$). You must guess the number from $1$ to $c$ $t$ times, using $\leq k$ queries. All $t$ games will be played consecutively and are independent.

第一行包含三个整数 $t$、$k$、$c$（$1 \leq t \leq 10^4$，$\mathbf{k = 4}$，$\mathbf{c = 4 \cdot 10^{18}}$）。你需要在 $t$ 轮游戏中，每轮从 $1$ 到 $c$ 的范围内猜出一个数，且每轮至多使用 $k$ 次询问。所有 $t$ 轮游戏将依次进行，且相互独立。

In the first game, the hidden number is $1000000_{10} = 100_{1000} = 11110100001001000000_2$. The sums of digits are $1$, $1$, and $7$ in these bases.

In the second game, the hidden number is $1$. The query with $b = 2$ returns $-1$.

In the third game, the hidden number is $42_{10} = 132_{5}$.

在第一局游戏中，隐藏的数字是 $1000000_{10} = 100_{1000} = 11110100001001000000_2$。这些进制下各位数字之和分别为 $1$、$1$ 和 $7$。

在第二局游戏中，隐藏的数字是 $1$。当查询 $b = 2$ 时，返回值为 $-1$。

在第三局游戏中，隐藏的数字是 $42_{10} = 132_{5}$。