406267: GYM102341 F Flaaffy

F. Flaaffytime limit per test15.0 smemory limit per test512 MBinputstandard inputoutputstandard output

So you want to see how Pokémon play games, eh? It's 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 $$$99\,999$$$. 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 two following ways:

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

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

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

Input

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

Output

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

ExampleInput

3
97 107
12043 12045
61 69

Output

6
5
7

Note

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.