题目背景

「历史自然会有判断，但我对历史的结论无甚兴趣。」
「事成，我此时便是胸有成竹，神闲气定。」
「事败，我此时便是逸乐无度，爱雀失众。」

一只雀儿跳下他的肩膀，他顺势抬手接住。

「我只是做了我的判断罢了。」

题目描述

Zemu 玩崩铁玩魔怔了。他决定搞点数学题练练脑子。

他现在给你了 $q$ 次询问，每次给定 $L,R$，求 $[L,R]$ 中第一个满足 $\phi(x)|x$ 的数 $x$，或报告不存在。

其中 $\phi$ 是欧拉函数，$\phi(n)$ 定义为 $1-n$ 中与 $n$ 互质的数的个数。

输入格式

第一行一个正整数 $q$。

接下来 $q$ 行，每行两个正整数 $L,R$。

输出格式

$q$ 行，若存在输出一个正整数，否则输出 $-1$。

样例 #1

样例输入 #1

6
2 3
3 4
5 7
114514 1919810
20071230 20120712
10000000000000 1000000000000000000

样例输出 #1

2
4
6
118098
-1
10030613004288

提示

对于 $100\%$ 的数据，$1\le q \le 5\times 10^5,1\le L \le R \le 10^{18}$。