G. 兄弟数
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

对于某个数正整数$$$t$$$，若存在一个正整数$$$r$$$，使得$$$t=r\times r$$$，则我们称$$$t$$$为 完全平方数 。

对于某个正整数$$$x$$$，存在某个正整数$$$y$$$，设$$$k=x\times y$$$，满足$$$k$$$为完全平方数，且$$$L \le k \le R$$$，则称$$$y$$$为$$$x$$$的 兄弟数 。

现在请你解决下面这个问题：

给出$$$x,L,R$$$,定义$$$y$$$是$$$x$$$的兄弟数，如果$$$y$$$存在，输出任意一个$$$y$$$，如果$$$y$$$不存在，则输出$$$-1$$$。

Input

第一行输入一个正整数$$$T$$$，表示共有$$$T$$$组测试样例。

接下来输入$$$T$$$行，每行三个正整数$$$x,L,R$$$。

$$$1\le T\le 10^4 ,1 \le x \le 10^8,1\le L\le R\le 10^{16}$$$

Output

对于每一组测试样例，输出一个正整数，若存在$$$y$$$是$$$x$$$的兄弟数，则输出$$$y$$$，若不存在，则输出$$$-1$$$。

Example
Input
3
27 954 8653
49 351 1294
65 754 1533
Output
48
9
-1