점프

개구리가 수직선 위의 0에서 출발해서 오른쪽(x좌표가 증가하는 방향)으로 점프를 수행한 후 어떤 수 x > 0에 도착하려 한다. 이때 점프 간격은 1부터 시작해서 항상 직전 점프 간격의 2배로 증가해야 한다.

점프 간격을 2배씩 계속 늘리다 보면 마지막 점프에서 목표 수 x를 지나칠 수 있다. 이때는 필요하면 언제든지 점프 간격을 다시 1로 되돌릴 수 있다. 이것을 재시작이라고 한다. 예를 들어 <그림 1>처럼 x = 19에 도달하려면 재시작을 2번 해서 (1+2+4+8)+(1+2)+(1)=19, 즉 7번의 점프로 도착할 수 있다.

<그림 1>

개구리가 0에서 출발해 양의 정수 N에 도달하는 데 필요한 점프 횟수의 최솟값을 J(N)이라 하고, 이를 N의 점프넘버라고 부른다. 예를 들어 <그림 1>에서 J(1)=1, J(3)=2, J(7)=3, J(15)=4, J(16)=5, J(18)=6, J(19)=7임을 알 수 있다.

구간 [x, y] 안의 수들의 점프넘버 중 최댓값을 찾아 출력한다. 즉 다음을 만족하는 w를 구한다.

$w = \max\{J(i) \mid x \le i \le y\}$

첫 줄에 구간의 개수 T가 주어진다 ($1 \le T \le 2{,}000$). 이후 T개의 줄에 답을 구해야 할 구간을 나타내는 두 정수 x, y가 공백으로 구분되어 주어진다 ($1 \le x \le y \le 10^9$).

T개의 줄에 각각 구간 [x, y] 안의 수들의 점프넘버 중 최댓값을 하나의 정수로 출력한다. 출력 순서는 입력으로 주어진 구간의 순서와 같아야 한다. 즉 첫 번째 줄에는 첫 번째 구간에 대한 정답을 출력한다.