10876번 - 사전 조사

오늘도 심심한 지학이는 A 이상 B 이하의 각 자연수가 하나씩 들어 있는 사전을 만들었다. 지학이는 사전의 각 페이지에 정확히 하나의 자연수를 적었기 때문에, 사전은 총 B − A + 1페이지로 구성되어 있다. 사전에 있는 자연수들은 크기순이 아닌 사전 순으로 적혀 있다. 예를 들어 A = 4, B = 12라면 자연수들이 10, 11, 12, 4, 5, 6, 7, 8, 9의 순으로 적혀 있는 것이다.

지학이는 심심해 보이는 수찬이에게 자신이 만든 사전을 건네주면서 사전에는 연속하는 자연수들이 사전 순으로 적혀있다고 귀띔하였다. 매우 심심했던 수찬이는 사전에 과연 어떤 자연수들이 적혀 있는지 알고 싶었다. 사전에는 페이지 번호가 적혀 있지 않기 때문에 수찬이는 어떠한 짐작도 하지 못한 채 사전을 앞에서부터 한 페이지씩 차례대로 읽을 수밖에 없었다. 하지만 수찬이는 사전의 모든 페이지를 다 읽은 순간 표지를 보고 그 사실을 알 수 있다. 수찬이는 가능한 적은 수의 페이지를 읽어 A와 B 의 값을 찾아내고 싶어한다.

A와 B 가 주어질 때, 수찬이가 지학이의 사전을 받고 A와 B 의 값을 모두 알아내기 위해 읽어야 할 최소한의 페이지 수를 구하는 프로그램을 작성하라.

첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 10⁵)가 주어진다. 이후 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄로 구성되며, 이 줄에는 A와 B (1 ≤ A ≤ B ≤ 10¹⁸)가 공백을 사이로 두고 입력된다. 이는 지학이가 A 이상 B 이하의 자연수들로 구성된 사전을 만들었음을 의미한다.

각 테스트 케이스에 대해, 수찬이가 읽어야 할 최소 페이지 수를 한 줄에 하나씩 출력한다.

각 테스트 케이스마다 사전을 앞에서부터 차례로 읽어나가면 아래와 같다.

• #1: 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9
• #2: 10, 11, 12, 13, 5, 6, 7, 8, 9
• #3: 3, 4, 5