Hide

Divisibility 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

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 4.1medium
Statistics Show