CF1543D2.RPD and Rap Sheet (Hard Version)

This is the hard version of the problem. The only difference is that here $2\leq k\leq 100$. You can make hacks only if both the versions of the problem are solved.

This is an interactive problem!

Every decimal number has a base $k$ equivalent. The individual digits of a base $k$ number are called $k$-its. Let's define the $k$-itwise XOR of two $k$-its $a$ and $b$ as $(a + b)\bmod k$.

The $k$-itwise XOR of two base $k$ numbers is equal to the new number formed by taking the $k$-itwise XOR of their corresponding $k$-its. The $k$-itwise XOR of two decimal numbers $a$ and $b$ is denoted by $a\oplus_{k} b$ and is equal to the decimal representation of the $k$-itwise XOR of the base $k$ representations of $a$ and $b$. All further numbers used in the statement below are in decimal unless specified.

You have hacked the criminal database of Rockport Police Department (RPD), also known as the Rap Sheet. But in order to access it, you require a password. You don't know it, but you are quite sure that it lies between $0$ and $n-1$ inclusive. So, you have decided to guess it. Luckily, you can try at most $n$ times without being blocked by the system. But the system is adaptive. Each time you make an incorrect guess, it changes the password. Specifically, if the password before the guess was $x$, and you guess a different number $y$, then the system changes the password to a number $z$ such that $x\oplus_{k} z=y$. Guess the password and break into the system.

这是该问题的困难版本。唯一的区别在于此处 $2\leq k\leq 100$。仅当两个版本的问题均被解决时，你才可进行 hack。

这是一个交互式问题！

每个十进制数都有一个对应的 $k$ 进制表示。$k$ 进制数的各位数字被称为 $k$-its（$k$ 进制位）。我们定义两个 $k$-its $a$ 和 $b$ 的 $k$-itwise XOR（按 $k$ 进制位异或）为 $(a + b)\bmod k$。

两个 $k$ 进制数的 $k$-itwise XOR 定义为：对它们对应位置上的 $k$-its 分别进行 $k$-itwise XOR 运算后所形成的新 $k$ 进制数。两个十进制数 $a$ 和 $b$ 的 $k$-itwise XOR 记作 $a\oplus_{k} b$，其值等于 $a$ 与 $b$ 的 $k$ 进制表示逐位进行 $k$-itwise XOR 后所得结果的十进制表示。以下陈述中所有未特别说明的数字均为十进制。

你已成功入侵了 Rockport 警察局（RPD，又称 Rap Sheet）的罪犯数据库。但要访问该数据库，你需要输入密码。你并不知道密码，但你确信它一定在 $0$ 到 $n-1$（含端点）之间。因此，你决定尝试猜测密码。幸运的是，你在被系统封锁前最多可尝试 $n$ 次。但该系统是自适应的：每次你猜错时，密码都会发生变化。具体而言，若猜之前密码为 $x$，而你猜了一个不同的数 $y$，则系统会将密码更改为某个数 $z$，使得 $x\oplus_{k} z=y$。请猜出密码并成功入侵系统。

The first line of input contains a single integer $t$ ($1\leq t\leq 10\,000$) denoting the number of test cases. $t$ test cases follow.

The first line of each test case contains two integers $n$ ($1\leq n\leq 2\cdot 10^5$) and $k$ $(2\leq k\leq 100)$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

输入的第一行包含一个整数 $t$（$1\leq t\leq 10\,000$），表示测试用例的数量。接下来是 $t$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$（$1\leq n\leq 2\cdot 10^5$）和 $k$（$2\leq k\leq 100$）。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

Test Case 1:

In this case, the hidden password is $2$.

The first query is $3$. It is not equal to the current password. So, $0$ is returned, and the password is changed to $1$ since $2\oplus_2 1=3$.

The second query is $4$. It is not equal to the current password. So, $0$ is returned, and the password is changed to $5$ since $1\oplus_2 5=4$.

The third query is $5$. It is equal to the current password. So, $1$ is returned, and the job is done.

Test Case 2:

In this case, the hidden password is $3$.

The first query is $1$. It is not equal to the current password. So, $0$ is returned, and the password is changed to $7$ since $3\oplus_3 7=1$. $[3=(10)_3$, $7=(21)_3$, $1=(01)_3$ and $(10)_3\oplus_3 (21)_3 = (01)_3]$.

The second query is $4$. It is not equal to the current password. So, $0$ is returned, and the password is changed to $6$ since $7\oplus_3 6=4$. $[7=(21)_3$, $6=(20)_3$, $4=(11)_3$ and $(21)_3\oplus_3 (20)_3 = (11)_3]$.

The third query is $6$. It is equal to the current password. So, $1$ is returned, and the job is done.

Note that these initial passwords are taken just for the sake of explanation. In reality, the grader might behave differently because it is adaptive.

测试用例 1：

本例中，隐藏的密码为 $2$。

第一次查询为 $3$。它不等于当前密码，因此返回 $0$；同时密码更新为 $1$，因为 $2\oplus_2 1=3$。

第二次查询为 $4$。它不等于当前密码，因此返回 $0$；同时密码更新为 $5$，因为 $1\oplus_2 5=4$。

第三次查询为 $5$。它等于当前密码，因此返回 $1$，任务完成。

测试用例 2：

本例中，隐藏的密码为 $3$。

第一次查询为 $1$。它不等于当前密码，因此返回 $0$；同时密码更新为 $7$，因为 $3\oplus_3 7=1$。$[3=(10)_3$, $7=(21)_3$, $1=(01)_3$，且 $(10)_3\oplus_3 (21)_3 = (01)_3]$。

第二次查询为 $4$。它不等于当前密码，因此返回 $0$；同时密码更新为 $6$，因为 $7\oplus_3 6=4$。$[7=(21)_3$, $6=(20)_3$, $4=(11)_3$，且 $(21)_3\oplus_3 (20)_3 = (11)_3]$。

第三次查询为 $6$。它等于当前密码，因此返回 $1$，任务完成。

注意：这些初始密码仅为解释目的而设定。实际上，评测程序可能表现不同，因为它具有自适应性。