제국의 도로

왕이 죽었다. 새 왕이여, 만세!

젊은 황제가 아버지의 광대한 제국을 물려받았다. 성공적인 통치 끝에 제국에는 도시가 너무 많아서, 무한히 많다고 봐도 무리가 없을 정도다.

그러나 제국의 교통 체계는 형편없다. 모든 새 통치자가 그러하듯, 황제는 선대의 정책을 바꾸고자 한다. 그래서 전쟁 대신 제국에 새 도로를 몇 개 건설하기로 했다. 다만 제국의 종교적 신념 때문에 황제는 새 도로를 건설할 때 정해진 의식을 따라야 한다.

먼저 양의 정수 $n$을 하나 정한다. 그다음 $n$개의 도시를 골라 $1$부터 $n$까지 번호를 붙인다. 이후 $1 \leq x < y \leq n$인 모든 도시 쌍 $(x, y)$에 대해, $x + n$이 $y$로 나누어떨어질 때에만 두 도시를 잇는 도로를 건설한다.

이 모든 과정을 마친 뒤 황제는 $1 \leq u, v \leq n$인 두 도시 $u$와 $v$를 골라, 두 도시 사이 최단 경로에 있는 도로의 개수를 구해야 한다. 게다가 제국의 수호신인 신의 축복을 받으려면 두 도시를 무작위로, 같은 확률로 골라야 한다. 이 길이를 알면 종교 회의에서 계획이 받아들여질 만한지 결정할 것이다.

황제는 회의를 앞두고 걱정이 많아 이런 계획을 여러 개 준비했다. 각 계획마다 최단 경로의 길이를 구하라!

첫째 줄에 정수 $T$가 주어진다. ($1 \leq T \leq 2 \cdot 10^5$) 이는 황제가 제안한 계획의 수다.

다음 $T$개의 줄에는 각각 세 정수 $n, u, v$가 주어진다. ($1 \leq n \leq 10^{18}, 1 \leq u, v \leq n$) $n$은 계획에서 고른 도시의 수이고, $u$와 $v$는 설명한 그래프에서 최단 경로의 길이를 구해야 하는 두 도시다.

각 테스트에서 $u$와 $v$는 $n$이 정해진 뒤 무작위로, 같은 확률로 골라졌음이 보장된다.

각 질의마다 해당 두 도시 사이 최단 경로의 길이를 한 줄에 하나씩 출력한다. 경로가 존재하지 않으면 $-1$을 출력한다.