407669: GYM102868 G White

White has navigated through the treacherous hallways of the map to reach the admin room where she is hopefully safe from the imposters. As she went to do the id card swipe, however, she realized that she dropped her wallet somewhere on the map. After determining that it was too unsafe to go retrieve her wallet, she decides to try to salvage the task by engaging the backup verification system which lets her enter her unique id code into the system.

Trouble is that she can't seem to remember her exact id code but she does remember how the id code was computed. Given an input $$$x$$$, the id creation function creates another number $$$\phi(x)$$$ by replacing every digit $$$y$$$ in $$$x$$$ with it's 'mirror' digit, $$$9 - y$$$ (and then stripping all leading zeros). It then returns the product of $$$x$$$ and $$$\phi(x)$$$ as your id code. (For example, if $$$40$$$ was passed into the function then $$$\phi(40) = 59$$$ so the id code would be $$$40 \cdot 59 = 2360$$$). Now, White was given a range of possible inputs to the function when she first created her id and she chose the input that gave her the maximum possible integer as her id code (which in hindsight is probably the reason she can't remember her code).

Unfortunately, she is not quite sure on what interval she was first given so she gives you $$$t$$$ candidate intervals, where the $$$i$$$th interval is of the form $$$[l_i,r_i]$$$, and would like you to compute what the value of her id code would be for that interval of numbers (aka for each interval $$$[l_i,r_i]$$$, compute the maximum possible product of $$$x$$$ and $$$\phi(x)$$$ where $$$l_i \leq x \leq r_i$$$).

The first line will contain a single integer, $$$t$$$, representing the number of intervals that will be given ($$$1 \leq t \leq 1000$$$).

The following $$$t$$$ lines will each contain two space-separated integers, so the $$$i$$$th line will have $$$l_i$$$ and $$$r_i$$$, where $$$1 \leq l_i \leq r_i \leq 10^{9}$$$, representing the bounds on the value of $$$x$$$ used to compute the id code for that interval.

Output $$$t$$$ lines each containing a single integer representing the id code of White for that interval of numbers (the maximum product of $$$x$$$ and $$$\phi(x)$$$ where $$$l_i \leq x \leq r_i$$$).

3
1 7
7 10
8 14

20
890
1190

In the first interval of the sample test case, if you choose $$$x = 4$$$ then we get $$$\phi(x) = 5$$$ which yields us the maximum possible id code of $$$20$$$.