考虑大小为 $k$ 的字母表 $\Sigma = \{s_0, \dots, s_{k-1}\}$。定义字符串序列 $\{T_i\}$ 如下：

• $T_0 = s_0$;
• $T_i = T_{i-1} s_{i \bmod k}$，对于所有整数 $i \ge 1$。

令 $S = T_0 T_1 T_2 \dots$ 为一个无限字符串，它是所有字符串 $\{T_i\}$ 按索引升序连接而成的。例如，若 $k = 3$，$s_0 = \text{“a”}$，$s_1 = \text{“b”}$，$s_2 = \text{“c”}$，则 $T_0 = \text{“a”}$，$T_1 = \text{“ab”}$，$T_2 = \text{“abc”}$，$T_3 = \text{“abca”}$，$T_7 = \text{“abcabcab”}$（依此类推），且 $S = \text{“aababcabcaabcab}\dots\text{”}$。

用 $S_n$ 表示字符串 $S$ 的长度为 $n$ 的前缀。给定数字 $n$ 和 $k$，计算字符串 $S_n$ 中不同非空子串的数量，其中 $|\Sigma| = k$。

输入格式

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

接下来 $T$ 行，第 $i$ 行包含两个整数 $n_i$ 和 $k_i$ ($1 \le n_i \le 10^9, 1 \le k_i \le 10^9$)，由空格分隔，分别表示第 $i$ 个测试用例中字符串 $S_{n_i}$ 的长度和字母表 $\Sigma$ 的大小。

输出格式

输出 $T$ 行。第 $i$ 行应包含一个整数，表示第 $i$ 个测试用例的答案。

样例

输入 1

7
1 3
2 3
3 3
4 3
5 3
6 3
7 3

输出 1

1
2
5
8
11
17
23