Description:
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.
Input Format:
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$$$.
Output Format:
None
Note:
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.