最努力的活着

Problem Description

小 E 在仿照约瑟夫问题进行模拟游戏，游戏规则是这样的：

• 有 $n$ 个人排成一排，每个人都有一个价值。游戏初始有一个参数 $1\leq w\leq n$。
• $n$ 个人的位置下标从 $1$ 开始算，即 $1,2,\cdots, n$。
• 每一轮，首先统计当前在场的所有人的价值和，计入 sum。
• 再查看当前剩余人数，如果 $<w$，游戏结束。
• 如果游戏没有结束，淘汰所有位置下标是 $w$ 的倍数的人，人的下标从 $1$ 开始编号，所有淘汰结束后，未被淘汰的人按照从左到右重新编号。并重新开始新的一轮。 小 E 的目标是最大化最终得到的 sum，而 ta 唯一能决定的是初始每个人的价值。 已知这 $n$ 个人的价值序列恰好是 $1,2,\dots, n$ 的排列，位置可以任意安排，求能得到的最大 sum。

Input

本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。 对于每组测试数据：一行包含两个正整数 $n,w$，分别表示总人数和初始参数。

Output

对于每组测试数据，输出一行一个正整数，表示能够获得的最大总价值。

Sample Input

4
5 2
7 4
6 1
9 3

Sample Output

41
120
21
155

Hint

对于所有数据，$1\leq T\leq 20$，$1\leq n ≤ 10^{12}$，$1\leq w\leq n$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（8）