维卡最喜欢的化妆品店“金梨”引入了新的奖励系统!
系统的工作原理如下:假设客户有 $$$b$$$ 奖金。在付款之前,客户可以选择以下两个选项之一:
- 获得等于当前奖金数量的折扣,同时不扣除奖金。
- 累积额外的 $$$x$$$ 奖金,其中 $$$x$$$ 是数字 $$$b$$$ 的最后一位数字。结果,客户的账户将有 $$$b+x$$$ 奖金。
例如,如果客户有 $$$24$$$ 奖金,他可以享受 $$$24$$$ 折扣或累积额外 $$$4$$$ 奖金,之后他的账户将有 $$$28$$$ 奖金。
目前,Vika 已经累积了 $$$s$$$ 奖金。
女孩知道,在奖金系统的剩余时间内,她将在“金梨”商店网络上进行 $$$k$$$ 的更多购买。
在熟悉了奖金系统的规则后,维卡开始对她可以获得的最大总折扣感兴趣。
帮女孩回答一下这个问题。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。
测试用例由一行组成,其中包含两个整数 $$$s$$$ 和 $$$k$$$ ($$$0 \le s \le 10^9$$$, $$$1 \le k \le 10^9$$$) - Vika 帐户中当前的奖金数量以及女孩还将进行多少次购买。
输出
对于每个测试用例,输出一个整数——通过奖金系统可以获得的最大总折扣。
示例
输入 #1
6 1 3 11 3 0 179 5 1000000000 723252212 856168102 728598293 145725253
输出 #1
4 33 0 9999999990 1252047198518668448 106175170582793129
注意
在第一个测试用例中,Vika 在第一次和第二次购买后可以累积奖金,之后她可以获得 $$$4$$$ 的折扣。
在第二个测试用例中,Vika 可以获得 3 次 $$$11$$$ 折扣,总折扣为 $$$33$$$。
在第三个示例中,无论 Vika 采取什么行动,她总是会获得 $$$0$$$ 的总折扣。