Chasing

Interview

Time limit1sMemory limit256 MB

Summary

Compute how many turns pass until a tortoise moving one section per turn and a hare moving two meet on a circular track.

Level: Medium5 of 10
Topics: Math
Solved: No attempts yet

Problem

A tortoise and a hare chase each other on a circular track made of $N$ sections. The sections are numbered $1, 2, \dots, N$ , and section $1$ comes right after section $N$ . The track is one way. From section $i$ the only move is to section $i+1$ , and from section $N$ the only move is to section $1$ .

When the race starts, the hare is on section $R$ and the tortoise is on section $T$ . A turn begins with the tortoise, which moves forward one section, and then the hare moves forward two sections. The race ends the moment both animals are on the same section, which can happen before the hare has finished its two sections. One turn counts the tortoise's move and the hare's move together. If the two are already on the same section before anyone moves, the race ends at once and takes $0$ turns.

Given the size of the track and the two starting sections, write a program that finds how many turns the race takes.

Input

The first line has the number of test cases $K$ ( $1 \le K \le 100{,}000$ ).

Each of the next $K$ lines has three integers $N_i$ , $R_i$ , $T_i$ ( $1 \le N_i \le 10^{18}$ , $1 \le R_i, T_i \le N_i$ ): the size of the track, the hare's starting section, and the tortoise's starting section of the $i$ -th test case.

Output

Print $K$ lines. The $i$ -th line has the number of turns the $i$ -th test case takes.

Examples2

Example 1
Input
```
4
10 1 4
10 8 3
10 2 10
20 5 5
```
Expected output
```
3
5
8
0
```
Example 2
Input
```
4
1 1 1
2 1 1
2 1 2
2 2 1
```
Expected output
```
0
0
1
1
```