17613번 - 점프

개구리가 수직선 위의 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) | x ≤ i ≤ y}

첫 번째 줄에는 여러분에게 주어질 구간의 개수 T가 주어진다.(1 ≤ T ≤ 2,000) 이후 T개의 줄에 대해 답을 구해야 할 구간을 나타내는 두 정수 x, y가 공백을 사이에 두고 주어진다 (1 ≤ x ≤ y ≤ 10⁹).

T개의 줄에 각각 하나의 정수를 출력한다. 각 줄에 출력되는 정수는 구간 [x, y]안의 수들의 점프넘버들 중 최댓값이다. 각 정수는 입력으로 주어지는 구간의 순서에 맞게 출력되어야 한다. 즉, 첫 번째 줄에 출력되는 정답은 첫 번째로 주어지는 구간에 대응되어야 한다.