Vika and Bonuses
Contest: Codeforces Round 885 (Div. 2)
Difficulty rating: 2200
Tags: binary search, brute force, math, ternary search

A new bonus system has been introduced at Vika's favorite cosmetics store, "Golden Pear"!

The system works as follows: suppose a customer has $$$b$$$ bonuses. Before paying for the purchase, the customer can choose one of two options:

- Get a discount equal to the current number of bonuses, while the bonuses are not deducted.
- Accumulate an additional $$$x$$$ bonuses, where $$$x$$$ is the last digit of the number $$$b$$$. As a result, the customer's account will have $$$b+x$$$ bonuses.

For example, if a customer had $$$24$$$ bonuses, he can either get a discount of $$$24$$$ or accumulate an additional $$$4$$$ bonuses, after which his account will have $$$28$$$ bonuses.

At the moment, Vika has already accumulated $$$s$$$ bonuses.

The girl knows that during the remaining time of the bonus system, she will make $$$k$$$ more purchases at the "Golden Pear" store network.

After familiarizing herself with the rules of the bonus system, Vika became interested in the maximum total discount she can get.

Help the girl answer this question.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.

The test case consists of a single line containing two integers $$$s$$$ and $$$k$$$ ($$$0 \le s \le 10^9$$$, $$$1 \le k \le 10^9$$$) — the current number of bonuses in Vika's account and how many more purchases the girl will make.

Output format:
For each test case, output a single integer — the maximum total discount that can be obtained through the bonus system.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Vika can accumulate bonuses after the first and second purchases, after which she can get a discount of $$$4$$$.

In the second test case, Vika can get a discount of $$$11$$$ three times, and the total discount will be $$$33$$$.

In the third example, regardless of Vika's actions, she will always get a total discount of $$$0$$$.

Example input:
6
1 3
11 3
0 179
5 1000000000
723252212 856168102
728598293 145725253

Example output:
4
33
0
9999999990
1252047198518668448
106175170582793129

Editorial:
First, let's note that the optimal strategy for Vika will be to accumulate bonuses first and then only get the discount. This simple observation is proved by greedy considerations.
Next, let's note that the last digit of the bonus number will either become zero after a few actions (in which case it makes no sense for Vika to accumulate more bonuses), or it will cycle through the digits $$$2$$$, $$$4$$$, $$$8$$$, $$$6$$$.
To begin with, let's consider two options: whether Vika will accumulate bonuses at all or always choose the option to get the discount. In the second case, the answer is trivially calculated, but in the first case, we can use the above statement.
Now let's consider four options for the last digit. With a fixed last digit, we can simulate the first actions until we reach that last digit. Then we need to determine how many times we will "scroll" through the digits $$$2$$$, $$$4$$$, $$$8$$$, $$$6$$$ for the best result. Let's say that at the moment of obtaining the desired last digit, Vika has accumulated $$$b$$$ bonuses and she can perform $$$a$$$ more actions. Then, if the cycle is "scroll" $$$x$$$ times, the discount will be $$$(b + 20 \cdot x) \cdot (a - x)$$$. This is a parabola equation. Its maximum can be found using the formula for the vertex of a parabola or by ternary search.