금화 게임

해적은 멋진 직업처럼 보이지만 나름의 고충이 있다. 그중 하나는 아무 일도 일어나지 않는 날 망망대해에서 오랜 시간을 보내야 한다는 것이다. 지루함을 달래기 위해 해적들은 금화로 하는 여러 놀이를 즐긴다.

그중 두 해적이 하나의 금화 더미를 두고 하는 놀이가 있다. 두 사람은 번갈아 차례를 진행하며, 자기 차례가 되면 정수 $K$에 대해 $K$의 거듭제곱, 즉 $1, K, K^2, K^3, \dots$ 중 하나에 해당하는 개수만큼 금화를 가져갈 수 있다. 단, 남아 있는 금화보다 많이 가져갈 수는 없다. 마지막 금화를 가져가는 해적이 이긴다.

금화 더미에 남은 금화의 개수 $S$와 $K$가 주어질 때, 먼저 시작하는 해적이 반드시 이기려면 첫 번째 차례에 최소 몇 개의 금화를 가져가야 하는지 구하여라. 두 해적은 모두 최선을 다해 게임을 진행한다.

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 한 줄에 두 정수 $S$와 $K$로 이루어진다. $S$는 금화의 개수를, $K$는 한 차례에 $1, K, K^2, \dots$개의 금화를 가져갈 수 있음을 의미한다. ($1 \le S \le 10^9$, $1 \le K \le 100$)

각 테스트 케이스마다, 먼저 시작하는 해적이 이기기 위해 첫 번째 차례에 가져가야 하는 금화 개수의 최솟값을 한 줄에 출력한다. 어떤 개수를 가져가도 이길 수 없다면 $0$을 출력한다.