25557번 - 수 맞히기 게임 스페셜 저지

문제

원욱이와 성제는 수 맞히기 게임을 하고 있다. 게임은 다음과 같이 진행된다.

1. 원욱이가 $x$ 이상 $y$ 이하의 정수 중에서 하나를 선택한다. 선택한 정수를 $k$라고 하자. 성제는 $x$와 $y$가 얼마인지는 알지만, $k$의 값은 모른다.
2. 성제가 $x$ 이상 $y$ 이하의 정수 중 하나를 부른다. 이것을 질문 1ドル$회로 간주한다. 만약 부른 정수가 $k$와 같다면 즉시 게임이 끝난다.
3. 성제가 부른 정수가 $k$와 다르다면 원욱이는 성제에게 부른 정수가 $k$보다 큰지 작은지 알려준다.
4. 게임이 끝날 때까지 2, 3번 과정을 반복한다.

여러 번 게임을 한 후, 성제는 질문 횟수를 줄이기 위해 다음과 같은 전략을 세웠다.

• $k$가 될 수 있는 범위가 $a$ 이상 $b$ 이하일 때, 구간 $[\max(a,\lceil\frac{a+b}{2}-1\rceil),\min(b,\lfloor\frac{a+b}{2}+1\rfloor)]$에서 임의로 정수 하나를 뽑아서 그 수를 부른다. 구간에서 각각의 정수가 뽑힐 확률은 동일하다.

여러분은 성제의 전략이 얼마나 효과가 있는지 알아내야 한다. 주어지는 $x,ドル $y,ドル $k$에 대하여 게임이 끝날 때까지 성제가 한 질문 횟수의 기댓값을 구하자!

입력

첫째 줄에 게임의 횟수 $N$이 입력된다. $(1 \le N \le 100,000円)$

다음 $N$개의 줄에는 각 게임에서 정해진 세 정수 $x,ドル $y,ドル $k$가 입력된다. $(-1,200円 \le x \le k \le y \le 1,200円)$

출력

$N$개의 줄에 각 게임에서 성제가 한 질문 횟수의 기댓값을 하나씩 출력한다. 출력한 답과 정답의 절대/상대 오차가 10ドル^{-7}$ 이하이면 정답이다.

제한

힌트