What a Twist

Time limit1sMemory limit128 MB

Summary

Find the maximum of n times its digitwise nine-complement over all integers from 1 to N for each test case.

Level: Medium5 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

The reversal $F(n)$ of a positive integer $n$ is the number you get by replacing every digit $a$ of $n$ with $9 - a$ .

Zeros that end up in front of the leading significant digit are ignored. So the reversal of 9 is 0, the reversal of 91 is 8, the reversal of 124 is 875, and the reversal of 990 is 9.

The loveliness of $n$ is $n$ multiplied by $F(n)$ .

The loveliness of 124 is 124 times 875, which is 108500

Given a positive integer $N$ , find the largest loveliness among the numbers from 1 to $N$ .

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 20000$ )

Each of the next $T$ lines contains one positive integer $N$ . ( $1 \le N \le 1000000000$ )

Output

For each test case, print on its own line the largest loveliness among the numbers from 1 to $N$ . The answer for the $k$ -th test case goes on the $k$ -th line.

Hint

Both 4 and 5 have loveliness 20, and 100 has loveliness 89900.

Examples6

Example 1
Input
```
2
7
100
```
Expected output
```
20
89900
```
Example 2
Input
```
1
1
```
Expected output
```
8
```

Example 3

Input

Expected output

Example 4

Input

Expected output

Example 5

Input

Expected output

Example 6
Input
```
1
1000000000
```
Expected output
```
8999999999000000000
```