보물 찾기

문제

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

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

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

1. 위치 $SS$를 조사한다.
2. 오른쪽으로 $11$칸 이동해, 위치 $S+1S\; +\; 1$를 조사한다.
3. 왼쪽으로 $22$칸 이동해, 위치 $S+1-2S\; +\; 1\; -\; 2$를 조사한다.
4. 오른쪽으로 $33$칸 이동해, 위치 $S+1-2+3S\; +\; 1\; -\; 2\; +\; 3$를 조사한다.
5. 왼쪽으로 $44$칸 이동해, 위치 $S+1-2+3-4S\; +\; 1\; -\; 2\; +\; 3\; -\; 4$를 조사한다.
6. 오른쪽으로 $55$칸 이동해, 위치 $S+1-2+3-4+5S\; +\; 1\; -\; 2\; +\; 3\; -\; 4\; +\; 5$를 조사한다.
7. ...

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

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

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

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

입력

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

출력

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

2
-2 3 0
4 8 6

5
4

9
-1 1 0
-2 1 0
-3 1 0
-1 2 0
-2 2 0
-3 2 0
-1 3 0
-2 3 0
-3 3 0

2
2
2
3
4
4
3
5
6