보물 찾기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

L < S < R일 때, S에서 시작한 좌우 교대 이동이 L이나 R에 처음 도달하는 단계를 구한다.

난이도: 보통10점 중 4점
유형: 수학, 구현, 시뮬레이션, 완전 탐색
정답자: 아직 제출이 없습니다

문제

당신은 친구인 다빈과 함께 아래와 같이 무한히 긴 수직선 위에서 보물찾기 놀이를 하고 있다.

먼저 당신은 수직선에 있는 서로 다른 두 위치 $L$ , $R$ 에 보물 두 개를 숨긴다. ( $L < R$ ) 아래는 숨긴 두 보물의 위치가 $L = -2$ , $R = 3$ 인 경우의 예시이다. 주황색으로 표시된 두 개의 칸에 보물이 숨겨져 있다.

당신이 보물 두 개를 숨긴 다음, 다빈이 보물을 찾기 시작한다. 다빈은 당신이 정한 시작 위치 $S$ 에서 시작해, 아래 단계들을 순서대로 수행하며 보물을 찾을 것이다. 시작 위치 $S$ 는 항상 두 보물의 위치 $L$ 과 $R$ 사이에 있다. ( $L < S < R$ ) 두 보물 중 하나의 보물을 찾으면 보물찾기 놀이가 끝난다.

위치 $S$ 를 조사한다.
오른쪽으로 $1$ 칸 이동해, 위치 $S + 1$ 를 조사한다.
왼쪽으로 $2$ 칸 이동해, 위치 $S + 1 - 2$ 를 조사한다.
오른쪽으로 $3$ 칸 이동해, 위치 $S + 1 - 2 + 3$ 를 조사한다.
왼쪽으로 $4$ 칸 이동해, 위치 $S + 1 - 2 + 3 - 4$ 를 조사한다.
오른쪽으로 $5$ 칸 이동해, 위치 $S + 1 - 2 + 3 - 4 + 5$ 를 조사한다.
...

즉, $x$ 번째 단계에서는, $x$ 가 짝수라면 오른쪽으로 $x-1$ 칸 이동하고 $x$ 가 홀수라면 왼쪽으로 $x-1$ 칸 이동해서 도착한 위치를 조사한다. 만약, 어떤 단계에서 조사한 칸에 보물이 있으면 보물찾기 놀이가 끝난다. 아래 그림은 $L = -2$ , $R = 3$ 이고 다빈의 시작 위치 $S = 0$ 인 경우의 보물찾기 놀이의 과정이다.

5번째 단계에서 조사한 위치 $-2$ 에 보물이 있으므로, 5번째 단계에서 보물찾기 놀이가 끝난다.

당신이 정하는 세 변수 $L$ , $R$ , $S$ 의 값에 따라서, 보물찾기 놀이가 끝나는 단계가 달라진다. 따라서, 당신은 세 변수 값의 조합을 여러 가지 시도해 보려 한다.

각 경우에 대해, 두 보물의 위치 $L$ , $R$ 과 다빈이 시작하는 위치 $S$ 가 주어졌을 때, 몇 번째 단계에서 보물찾기 놀이가 끝나는지 구하여라.

입력

첫 번째 줄에 당신이 시도해 볼 경우의 수 $T$ 가 주어진다. 이후 $T$ 개의 줄에, 각 경우에 대해 세 변수 $L$ , $R$ , $S$ 의 값이 공백으로 구분되어 주어진다.

출력

$T$ 개의 줄에 걸쳐, 각 경우에 몇 번째 단계에서 보물찾기 놀이가 끝나는지 출력한다.

제한

주어지는 모든 수는 정수이다.
$1 \le T \le 10\\,000$
$-100\\,000\\,000 \le L < S < R \le 100\\,000\\,000$

예제2

예제 1
입력
```
2
-2 3 0
4 8 6
```
예상 출력
```
5
4
```

예제 2

입력

예상 출력