题意描述

我们称正整数数对 $(a,b)$ 是好的当且仅当 $a\times b$ 是完全平方数。小诗现在已确定 $a$ 的取值，她想在 $[L,R]$ 中选择一个数作为 $b$，并最小化 $b$ 的值，如果不存在这样的 $b$ ，请输出 $-1$ ，否则输出这个最小值。

小诗会给你 $T$ 组询问，如果你成功回答了这 $T$ 组询问，她会奖励你 $100$ 分。

输入格式

第一行一个正整数 $T$ ，表示数据组数。

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

输出格式

$T$ 行，每行一个整数，表示答案。

样例

样例输入 #1

5
1 1 100
20 25 40
8 10 20
14 10 30
15 10 30

样例输出 #1

1
-1
18
14
15

样例 2~4 见下发文件。

数据范围

对于所有测试点， $1\leqslant T\leqslant 1000,1\leqslant a\leqslant 10^6,1\leqslant L,R\leqslant 10^{12}$ 。

特殊性质 A：保证 $L=1$ 。

特殊性质 B：保证 $a$ 是完全平方数。