Description

给定一个十进制数 $y$，请选择一个进制 $b$，使得 $y$ 转成 $b$ 进制后大于或等于 $b$ 进制下的 $l$，且每位均为 $0$ 到 $9$ 之间的数码。求最大的 $b$。

Input

第一行1个正整数 $T$，是数据组数

接下来 $T$ 行每行2个整数 $y,l$

Output

输出 $T$ 行，每行一个答案整数 $b$

Sample

input

2
2333 10
19260817 93

output

2333
2140090

Explanation

对第一组数据，当 $b=2333$ 时，$y_{(b)} = 10_{(b)} \ge l_{(b)}$，显然这是最优答案。

对第二组数据，当 $b=2140090$ 时，$y_{(b)} = 97_{(b)} \ge l_{(b)}$，可以证明这是最优答案。

Constraints

所有数据满足 $10\le l\le y\le 10^{18}$。每个测试点各20分：

1. $T=1,~y \le 10^4$
2. $T=1,~y \le 10^{9}$
3. $T=1$
4. $T\le500$
5. $T\le70000$

由于出题人太菜了，不知道怎么造比较强的数据。欢迎大家踊跃提供数据生成器和hack数据。