#### Start

2021-10-03 01:00 AKDT

## NWERC 2021 Tryouts (AU)

#### End

2021-10-03 05:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -57 days 22:09:28

4:00:00

0:00:00

# Problem DDivisibility Shortcut There is a well-known shortcut (or “trick”) for determining whether or not a non-negative integer $n$ is divisible by $3$:

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

2. 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