你正在进行一项巨大的项目，后天就是截止日期了。你还有一些时间，但你的身心已经疲惫不堪，头不停地磕在桌子上。

别担心！你有充足的咖啡供应——大家都知道咖啡含有咖啡因，而咖啡因能让你保持清醒。你可能注意到的一个问题是，咖啡能让你在一段时间内保持清醒，但之后你会更加疲惫。为了提高效率，你必须明智地使用你的“抗疲劳武器”。

我们使用体力 $S$ 来评估你的精力。在每一秒，你为项目贡献 $S$ 点完成度，之后你的体力会减少 1。当你的体力减少到 0 或更低时，你将失去控制并进入梦乡。

你可以在每一秒的开始喝一杯咖啡，效果持续 $C$ 秒。在咖啡生效期间，你不能喝下一杯咖啡，且你的体力会固定在开始时的数值。在此之后，你的体力会减少 $C+1$，即咖啡会额外导致 1 点体力消耗。

你的目标是在睡着之前最大化你的总完成度。给定 $S$ 和 $C$，求出能使总完成度最大化的最优计划。

输入格式

第一行包含一个整数 $T(1 \le T \le 10^5)$，表示测试用例的数量。

对于每个测试用例，只有一行，包含两个整数 $S, C (1 \le S, C \le 172\,800 = 2 \times 24 \times 60 \times 60)$，分别表示你的初始体力和咖啡生效时长。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示可能的最大总完成度。

样例

输入 1

4
1 2
2 1
10 4
172800 172800

输出 1

2
3
63
29859840000

说明

对于第一个样例，你可以在最开始喝咖啡，体力序列将为 $1, 1, -2$。

对于第二个样例，由于咖啡对你完全不起作用，你应该停止过量饮用并保持更健康的生活方式。

对于第三个样例，一种最优计划是在第 3 秒和第 7 秒的开始分别喝一杯咖啡，体力序列将为 $10, 9, 8, 8, 8, 8, 3, 3, 3, 3, -2$。