Flaaffy

So you want to see how Pokémon play games, eh? It is a good day for you. Flaaffy, a sheep-like electric Pokémon, just found an electronic Number Guessing Board™ and it wants to have fun with it!

The board is a five-digit electronic display that can show all integers from 0 to 99999. When Flaaffy turned it on, all five digits were initially set to 0. On its startup, the board chose a secret integer $x$ in the interval $[L, R]$. Flaaffy wants to guess this number. It can use electric shocks to operate the board in the following two ways:

• Change a single digit on the display.
• Ask the board whether $x$ is smaller, equal to, or larger than the number shown on the display.

The game ends if Flaaffy can correctly determine the hidden number.

However, each operation depletes the electricity stored by Flaaffy. Therefore, it wants to determine the hidden number with the minimum possible number of shocks. Flaaffy already figured out the optimal strategy. Can you?

The first line contains a single integer $t$ ($1 \le t \le 50$), the number of independent testcases. Each of the following $t$ lines describes one testcase and contains two integers $L$ and $R$ ($1 \le L < R \le 99999$).

For each testcase, output a single number: the minimum number of shocks Flaaffy needs to produce in order to correctly guess the hidden number.

Here is the decision tree for the first testcase:

Each edge means either changing one digit or comparing $x$ with the number currently on the display. In the leaves of the tree, Flaaffy is already sure what the hidden number is.