34227번 - 토너먼트

문제

SKH Soccer Tournament는 토너먼트 형식으로 최후의 승자가 되는 팀을 가려내는 축구 대회이다. 규칙은 다음과 같다.

• 현재 살아남은 팀이 $N$개라고 하자. $N$이 짝수라면, 현재까지 살아남은 팀 중 절반이 살아남고 나머지 절반은 탈락한다. $N$이 홀수라면, 부전승이 일어나 $\cfrac{N + 1}{2}$ 팀이 살아남고 나머지는 탈락한다.
• 살아남은 팀이 정확히 한 팀이 될 때까지 위 과정을 반복한다.

SKH Soccer Tournament의 개최자인 당신은 부전승이 일어나는 횟수를 최소로 하려고 한다. 부전승이 일어나는 횟수가 최소가 되도록 참가 팀의 수를 $a$팀 이상 $b$팀 이하로 정할 때, 부전승이 몇 번 일어날지 알아내라.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \leq T \leq 100,000円)$

이후 $T$개의 줄에 걸쳐, 각 줄마다 정수 $a,ドル $b$가 공백으로 구분되어 주어진다. $(2 \leq a \leq b \leq 10^{18})$

출력

$T$개의 줄에 걸쳐, 각 줄마다 각 테스트 케이스에 대해 부전승 횟수가 최소가 되도록 참가 팀의 수를 정했을 때 부전승 횟수를 출력한다.

제한

힌트