Description

jbgg 今天在幼儿园学了进制转换，现在 jbgg 有一个十进制正整数 $x$，jbgg 好奇是否存在这样一个进制 $p$，使得 $x$ 在 $p$ 进制表示下的各个位上的数相加等于 $y$。

比如：$51121$ 转化成 $20$ 进制后为 $\{6,7,16,1\}$，则各个位数相加的结果就是 $6 + 7 + 16 + 1 = 30$。

但由于 jbgg 的智力没到幼儿园水平，所以他来想让你来帮他解决这个问题。

Format

Input

本题有多组测试数据。

第一行一个正整数 $t\ (1 \leqslant t \leqslant 10^3)$，表示数据组数。

接下来 $t$ 行，每行两个正整数 $x, y\ (2 \leqslant x \leqslant 10 ^ {10},\ 1 \leqslant y \leqslant \lfloor\frac{x}{2} \rfloor)$，分别表示题面给出的 $x$ 和 $y$。

Output

对于每组数据输出一行一个整数。

如果存在进制满足题意，则输出一个大于 $1$ 的正整数 $p\ (2\leqslant p \leqslant 10^{18})$，表示你找到的进制数。如果有多个答案，输出任意一个都可通过。

如果不存在这样的进制，则输出 $-1$。

Samples

6
5 2
13 4
51121 30
16 4
114514 1
33 8

2
4
20
5
114514
6

Note

对于样例中前三个数： $(\underline{5})_{10} \to (\underline{1}\ \underline{0}\ \underline{1})_{2}$ : $1+0+1=2$;

$(\underline{1}\ \underline{3})_{10} \to (\underline{3}\ \underline{1})_{4}$ : $3+1=4$;

$(\underline{5}\ \underline{1}\ \underline{1}\ \underline{2}\ \underline{1})_{10} \to (\underline{6}\ \underline{7} \ \underline{16}\ \underline{1})_{20}$ : $6 + 7 + 16 + 1 = 30$。 $(x)_y$ 表示一个数在 $y$ 进制的表示下为 $x$。

Limitation

1s, 1024KiB for each test case.