Problem B
Divisibility Shortcut
There is a well-known shortcut (or “trick”) for determining whether or not a non-negative 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 space-separated 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 |
