题目描述

人类的本质是复读机。

$lrb$ 在聊天时特别喜欢发 “😍”，并且喜欢通过不断的复读来阴阳怪气自己的队友，从而获得快乐

某次复读时 $lrb$ 想通过发送 $k$ 条消息 “😍” ，并且使这 $k$ 条消息组成一个大小为 $k$ 的三角形

更确切地说，大小为 $k$ 的三角形表情。它由 $k$ 条消息组成。第一条信息包含一个 “😍” ，第二条包含两个 “😍” ，...，第 $k$ 条包含 $k$ 个 “😍”

例如，$k=3$ 的三角形由三条信息组成

😍
😍 😍
😍 😍 😍

为了防止无休止复读的出现，当一个人发送 $x$ 条消息后，如果同一个符号重复次数大于等于 $n$ 次，就会收到来自 $Cierra$ 的禁言套餐

如果 $lrb$ 在复读了 $x$ 条之后被禁言了，那他就不能继续再复读，只能扫兴的去学习

否则，他将不断复读，直到大小为 $k$ 的三角形被完全发送过去，因为这样就可以心满意足的看到队友戴着痛苦面具

例如 $n=4,k=3$

在发送完前两行后， $lrb$ 重复发送了 $3$ 个 “😍”，此时不会被禁言

当他发送完第三行后，此时已经重复发了 $6$ 个 “😍”，于是他收到了来自 $Cierra$ 的禁言，复读到此结束

请计算 $lrb$ 一共能发送多少 “😍”

输入格式

第一行包含一个整数 $T (1 \leq T \leq 10^4)$ ，表示接下来有 $T$ 组测试案例

每个测试案例包含两个整数 $n(1 \leq n \leq 10^{18})$ 和 $k(1 \leq k \leq 10^9)$

输出格式

每个测试案例输出一个整数，表示 $lrb$ 能够发送出的 “😍” 的数量

样例

样例输入

3
7 3
4 3
2 3

样例输出

6
6
3