Flaaffy

시간 제한15초메모리 제한512 MB

요약

다섯 자리 표시판으로 숨겨진 정수를 찾을 때, 숫자 변경과 비교 질의를 합한 최소 횟수를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 이분 탐색
정답자: 아직 제출이 없습니다

문제

포켓몬들이 게임을 어떻게 하는지 보고 싶다고? 좋은 날이네. 양처럼 생긴 전기 타입 포켓몬 Flaaffy가 전자식 숫자 맞히기 보드TM를 발견했고, 이걸로 놀고 싶어 한다!

이 보드는 0부터 99999까지의 모든 정수를 표시할 수 있는 5자리 전자 디스플레이다. Flaaffy가 전원을 켰을 때 다섯 자리는 모두 0으로 설정되어 있었다. 켜진 직후 보드는 구간 $[L, R]$ 에서 비밀 정수 $x$ 를 골랐다. Flaaffy는 이 숫자를 맞히려고 한다. 다음 두 가지 방식으로 보드를 조작하는 데 전기 충격을 사용할 수 있다:

디스플레이의 한 자리 숫자를 바꾼다.
디스플레이에 표시된 숫자보다 $x$ 가 작은지, 같은지, 큰지 보드에 묻는다.

Flaaffy가 숨겨진 숫자를 정확히 알아내면 게임이 끝난다.

그러나 모든 조작은 Flaaffy가 저장한 전기를 소모한다. 따라서 Flaaffy는 숨겨진 숫자를 가능한 한 적은 횟수의 충격으로 알아내려 한다. Flaaffy는 이미 최적의 전략을 찾아냈다. 너도 찾을 수 있겠어?

입력

첫 줄에는 독립적인 테스트 케이스의 개수를 나타내는 정수 $t$ ( $1 \le t \le 50$ )가 주어진다. 이어지는 $t$ 개의 줄에는 각각 하나의 테스트 케이스가 주어지며, 정수 $L$ 과 $R$ ( $1 \le L < R \le 99999$ )이 주어진다.

출력

각 테스트 케이스마다 Flaaffy가 숨겨진 숫자를 정확히 맞히는 데 필요한 최소 충격 횟수를 한 개의 수로 출력한다.

힌트

아래는 첫 번째 테스트 케이스의 결정 트리다:

트리의 각 간선은 한 자리 숫자를 바꾸는 조작 또는 $x$ 를 디스플레이에 현재 표시된 숫자와 비교하는 조작을 뜻한다. 트리의 잎에서는 Flaaffy가 숨겨진 숫자가 무엇인지 이미 확실히 안다.

예제1

예제 1
입력
```
3
97 107
12043 12045
61 69
```
예상 출력
```
6
5
7
```