406267: GYM102341 F Flaaffy
Description
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.
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?
InputThe 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$$$).
OutputFor each testcase, output a single number — the minimum number of shocks Flaaffy needs to produce in order to correctly guess the hidden number.
ExampleInput3 97 107 12043 12045 61 69Output
6 5 7Note
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.