Christina是理论物理领域的天才，但令人意外的是，她的数学并不是很好。

现在她发现了一个新的理论：假设两条世界线的偏移值分别为$x,y(x < y)$，那么存在一条特殊的世界线（我们称其为$(x,y)-$生成世界线），其偏移值为$max(gcd(i,j))(x \leq i < j \leq y )$。

通过这个理论，Christina可以计算得出在一定偏移值上限内的世界线偏移值传递闭包，可$x,y$是在是太大了，她根本计算不了！

于是Christina来找你帮忙。当然，计算传递闭包是一件很麻烦的事，因此你只需要帮助她计算给定两条偏移值分别为$x,y$的世界线，$(x,y)-$生成世界线为多少。

注意：$gcd(i,j)$表示$i,j$的最大公因数，例如$gcd(4,6)=2$；$max(f(x))(C)$表示满足条件$C$的所有$f(x)$中的最大值。

第一行一个整数$T(1 \leq T \leq 5000)$，表示Christina对你提出了$T$次询问。

接下来$T$行，每行两个整数$x,y(1 \leq x < y \leq 10^{18},y-x \leq 5000)$，分别表示两条给定世界线的偏移值。

$T$行，每行输出给定两条世界线的$(x,y)-$生成世界线偏移值。

取$i=100,j=200$，其最大公因数为100。可以证明这是最大的答案。