310538: CF1848D. Vika and Bonuses

D. Vika and Bonusestime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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

ExampleInput

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

Output

4
33
0
9999999990
1252047198518668448
106175170582793129

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$.

题目大意：
Vika最喜欢的化妆品店“金梨”引入了一套新的奖金系统。系统的工作方式如下：假设顾客有b个奖金。在付款前，顾客可以选择以下两种方式之一：
1. 获得相当于当前奖金数量的折扣，而奖金不会扣除。
2. 积累额外的x奖金，其中x是数字b的最后一个数字。因此，顾客账户将有b+x个奖金。
例如，如果顾客有24个奖金，他可以获得24的折扣，或者积累额外的4个奖金，之后他的账户将有28个奖金。
目前，Vika已经积累了s个奖金。她知道在奖金系统剩余的时间内，她将在“金梨”商店网络中再进行k次购买。在了解奖金系统的规则后，Vika对可以得到的最大总折扣感兴趣。帮助她回答这个问题。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^5）——测试用例的数量。接下来是测试用例的描述。
测试用例由一行组成，包含两个整数s和k（0≤s≤10^9，1≤k≤10^9）——Vika账户中当前的奖金数量和她将进行的额外购买次数。

输出数据格式：
对于每个测试用例，输出一个整数——通过奖金系统可以获得的最大总折扣。

示例：
输入：
6
1 3
11 3
0 179
5 1000000000
723252212 856168102
728598293 145725253

输出：
4
33
0
9999999990
1252047198518668448
106175170582793129

注意：
在第一个测试案例中，Vika可以在第一次和第二次购买后积累奖金，之后她可以获得4的折扣。
在第二个测试案例中，Vika可以获得11的折扣三次，总折扣为33。
在第三个示例中，无论Vika采取什么行动，她总是得到总折扣0。题目大意： Vika最喜欢的化妆品店“金梨”引入了一套新的奖金系统。系统的工作方式如下：假设顾客有b个奖金。在付款前，顾客可以选择以下两种方式之一： 1. 获得相当于当前奖金数量的折扣，而奖金不会扣除。 2. 积累额外的x奖金，其中x是数字b的最后一个数字。因此，顾客账户将有b+x个奖金。 例如，如果顾客有24个奖金，他可以获得24的折扣，或者积累额外的4个奖金，之后他的账户将有28个奖金。 目前，Vika已经积累了s个奖金。她知道在奖金系统剩余的时间内，她将在“金梨”商店网络中再进行k次购买。在了解奖金系统的规则后，Vika对可以得到的最大总折扣感兴趣。帮助她回答这个问题。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^5）——测试用例的数量。接下来是测试用例的描述。 测试用例由一行组成，包含两个整数s和k（0≤s≤10^9，1≤k≤10^9）——Vika账户中当前的奖金数量和她将进行的额外购买次数。 输出数据格式： 对于每个测试用例，输出一个整数——通过奖金系统可以获得的最大总折扣。 示例： 输入： 6 1 3 11 3 0 179 5 1000000000 723252212 856168102 728598293 145725253 输出： 4 33 0 9999999990 1252047198518668448 106175170582793129 注意： 在第一个测试案例中，Vika可以在第一次和第二次购买后积累奖金，之后她可以获得4的折扣。 在第二个测试案例中，Vika可以获得11的折扣三次，总折扣为33。 在第三个示例中，无论Vika采取什么行动，她总是得到总折扣0。