#1168. zxh的后宫管理系统

大家都认为 Sheauhaw 有一个庞大的后宫, 于是后宫管理系统应运而生. 该后宫管理系统为了满足 Sheauhaw 的特殊需求, 众生平等, 甚至可以录入任何实体的信息! 下面是该系统的运营方式:

后宫管理系统中一共存储了 $n$ 个实体的信息, 每个实体都有一个从 $1$ 到 $n$ 的编号. 你可以向后宫管理员 Zeondik 查询某个实体的编号, 管理系统会返回一个编号 $x$.

但是, 由于系统不稳定, 你暂时不能确定这个 $x$ 的正确性, 假设真实编号是 $k$. 好在你可以向 Sheauhaw 核实该返回值, 但是 Sheauhaw 比较神秘, 不会直接告诉你对或者错, 也不会直接告诉你编号, 而是用一种奇怪的方式核实: Sheauhaw 可以让你呈上一个整数 $y$, 然后大发慈悲地告诉你 $\gcd(k,y)$.

聪明无比的你一定有一个合适的 $y$ 的选择, 将这个数字告诉 Sheauhaw 可以准确地判断 $x$ 的正确性. 然而, Sheauhaw 喜欢小的东西, 管理员 Zeondik 要求你在所有合适的 $y$ 中挑选一个最小的 $y_m$ 告诉 Sheauhaw, 并检查你的 $y$ 是否最小. 但 $y$ 可能很大, 你只需要输出 $y$ 对 $920,011,128$ 取模的数值即可: 如果你的输出 $y'\equiv y_m\pmod{920,011,128}$, Zeondik 就会让你通过.

如果没有合适的 $y$, 输出 $-1$.

第一行一个整数 $T$, 表示查询次数.

每组数据输入一行, 每行两个整数 $n,x$, 表示编号范围和系统输出.

每组输出输出一行, 一行一个整数, 表示 $y$ 对 $920,011,128$ 取模后的值. 如果没有合适的选择, 输出 $-1$.

样例输入

3
10 1
10 4
10 7

样例输出

210
8
7

$1\le T<10$

$1\le k\le n\le 10^7$