A16725. Game of Scientists (Version 1)

两个版本对于 $k$ 和 $c$ 有不同的限制。解决其中一个版本不一定能解决另一个。你可能需要阅读两个版本。两种版本均禁用 Hack。

这是一个交互题。

在奥斯曼帝国时期，许多科学家在辛勤工作。你决定研究他们的日常生活，并偶然发现了一种当时流行的有趣游戏。一位科学家会想出一个整数 $x$，使得 $1 \leq x \leq c$。另一位科学家尝试猜测这个数字。他可以指定一个进制 $b$，其中 $2 \leq b \leq c$，并会收到以下响应：如果 $x \geq b$，那么返回 $x$ 在 $b$ 进制下的各位数字之和，否则返回 $-1$。

你写了一个程序，能够想出一个数字 $x$ 并响应查询。现在你想和它进行游戏，学习如何在不超过 $k$ 次提问内猜出答案。

第一行包含三个整数 $t$、$k$、$c$（$1 \leq t \leq 10^4$，$\mathbf{k = 4}$，$\mathbf{c = 4 \cdot 10^{18}}$）。你需要在 $t$ 轮游戏中，每轮在 $1$ 到 $c$ 之间猜出隐藏的数。每轮最多允许进行 $k$ 次查询，所有 $t$ 轮游戏逐次独立进行。

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

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

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