P4109 [HEOI2015] Pricing

In the market, many goods are priced like 999 yuan, 4999 yuan, 8999 yuan. They are essentially no different from 1000 yuan, 5000 yuan, and 9000 yuan, but psychologically they make people feel much cheaper, so this is a common pricing strategy used by merchants. However, in your view, such prices are absurd. Therefore, you define the absurdity of a price $p$ ($p$ is a positive integer) as follows: 1. First, treat $p$ as a string of digits (without leading $0$). 2. Then, if the last character of $p$ is $0$, remove it. Repeat this process until the last character of $p$ is not $0$. 3. Let the length of $p$ be $a$. If the last digit is $5$, the absurdity is $2a - 1$; otherwise, it is $2a$. For example, the absurdity of 850 is 3, for 880 it is 4, and the absurdity of 9999 is 8. Now, you want to sell an idle item. The acceptable price is within the range $[L, R]$. You want to choose a price with the lowest absurdity.

The first line of input contains a positive integer $T$, indicating the number of testdata. Each test case is on a separate line and contains two space-separated positive integers $L, R$, indicating the pricing interval.

For each test case, output the result on a separate line. If the price with the lowest absurdity is not unique, output the smallest one.

- For $20\%$ of the testdata, $L, R \leq 2000$. - For $100\%$ of the testdata, $T \leq 100$, $1 \leq L \leq R \leq 10^9$. Translated by ChatGPT 5