Problem A
Divisibility Shortcut
There is a wellknown shortcut (or “trick”) for determining whether or not a nonnegative integer $n$ is divisible by $3$:

Add up the digits in the base$10$ representation of $n$; call this sum $S_{10}(n)$.

If $S_{10}(n)$ is divisible by $3$, then $n$ is divisible by $3$.
It turns out that this idea can be generalized to other bases and divisors. Let $b \geq 2$ and $d \geq 1$ be integers. For any integer $n \geq 0$, define $S_ b(n)$ to be the sum of the digits in the base$b$ representation of $n$. We say that DS$\boldsymbol {(b,d)}$ holds ($\mathit{DS}$ stands for “divisibility shortcut”) if the following is true: for all integers $n \geq 0$, if $S_ b(n)$ is divisible by $d$, then $n$ is divisible by $d$.
Given integers $b \geq 2$ and $k \geq 1$, find the largest integer $d \leq k$ such that $\mathit{DS}(b,d)$ holds.
Input
The first line of input contains an integer $T$ $(1 \leq T \leq 100)$, the number of test cases. This is followed by $T$ lines, one per test case, each of which contains two spaceseparated integers, $b$ and $k$ ($2 \leq b \leq 10^9$, $1 \leq k \leq 10^9)$.
Output
For each test case, output a single line containing the largest integer $d \leq k$ such that $\mathit{DS}(b,d)$ holds.
Sample Input 1  Sample Output 1 

2 10 5 24 11 
3 1 