G - Ganando Monedas

Time limit: 2 s
Memory limit: 256 MiB
Languages: C, C++, Java, Pascal, ... (details)

Durante su último viaje por el océano Fito se encontró con unos piratas. Estos le propusieron jugar a un juego relacionado con monedas de oro y captaron su atención inmediatamente. El juego consiste en que dos jugadores (Fito y uno de los piratas) alternan turnos quitando monedas de un cofre. Inicialmente hay $S$ monedas en el cofre y en cada turno un jugador puede quitar una cantidad de monedas que sea potencia de $K$ $(1, K^2, K^3,…)$. El ganador es el jugador que se lleva la última moneda y como premio se llevará todas las monedas que había inicialmente en el cofre. Fito no quiere perder esta oportunidad y nos contactó rápidamente para que lo ayudáramos. Cada vez que le toque su turno nos dirá la cantidad de monedas que hay en el cofre y nuestra tarea es decirle, en caso de que tenga posibilidades de ganar aun cuando el pirata juegue de forma óptima, la cantidad de monedas que debe retirar para asegurar que sigue con posibilidades de ganar. Si hay varias opciones él quiere que le digamos la menor para que así el juego sea más largo y el pirata no sospeche que hizo trampa.

Input

La entrada contiene varias preguntas de Fito y la primera línea contiene un entero $T$ $(1 \le T \le 100)$ que indica cu á ntas serán. Para cada pregunta habrá una línea con dos enteros $S$ $(1 \le S \le 10^9)$ y $K$ $(1 \le K \le 100)$ que representan la cantidad de monedas del cofre y el entero $K$ del enunciado respectivamente.

Output

Para cada pregunta de Fito la salida debe contener una línea con un entero que indica la cantidad de monedas que debe retirar Fito, o un 0 en caso de que Fito no pueda asegurar la victoria.

Sample test(s)

Input
5 5 1 3 2 8 2 50 3 100 10
Output
1 0 2 0 1