国王驾崩了。国王万岁！

年轻的皇帝刚刚继承了他父亲广阔的帝国。在先王成功的统治下，帝国拥有的城市数量之多，以至于可以认为它们有无穷多个。

然而，帝国的交通系统非常落后。像所有新统治者一样，皇帝想要改变他前任的政策。因此，他决定不再发动战争，而是要在帝国中修建一些新的道路。然而，国家的宗教信仰要求皇帝遵循一种特定的仪式来修建新道路。

首先，他必须选择一个正整数 $n$。然后，选取 $n$ 座城市，编号从 $1$ 到 $n$。之后，对于所有满足 $1 \le x < y \le n$ 的城市对 $(x, y)$，当且仅当 $x + n$ 能被 $y$ 整除时，在它们之间修建一条道路。

在完成所有这些操作后，皇帝必须选择两座城市 $u$ 和 $v$（满足 $1 \le u, v \le n$），并找出它们之间最短路径的长度。此外，为了得到帝国神圣守护者的祝福，他必须随机且等概率地选择这两座城市。在得知这个长度后，宗教委员会将决定该计划是否可以接受。

皇帝在与委员会会面之前感到担忧，因此他准备了几个这样的计划。对于每个计划，请回答最短路径的长度问题！

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2 \cdot 10^5$)，表示皇帝提出的计划数量。

接下来的 $T$ 行中，每行包含三个整数 $n, u, v$ ($1 \le n \le 10^{18}, 1 \le u, v \le n$)，分别表示为该计划选择的城市数量，以及要求找出最短路径的两座城市。

保证在每个测试用例中，$u$ 和 $v$ 都是在选定 $n$ 后随机且等概率选择的。

输出格式

对于每个查询，在单独的一行中打印一个数字，即对应城市之间的最短路径长度。如果路径不存在，则打印 $-1$。

样例

样例输入 1

4
5 1 2
8 2 5
7 7 2
6 2 5

样例输出 1

1
1
-1
2

样例输入 2

1
88 14 2

样例输出 2

2