题目描述

语言学家 Arin 正在研究一个无限长的字符串。给定一个大小为 $k$ 的字母表

$$\Sigma=\{s_0,s_1,\ldots,s_{k-1}\}.$$

定义一列字符串 $T_i$：

• $T_0=s_0$；
• 对所有 $i\ge 1$，

$$T_i=T_{i-1}s_{i\bmod k}.$$

也就是说，每一步都在前一个字符串后面追加一个按下标循环出现的字符。

再定义无限字符串

$$S=T_0T_1T_2\cdots,$$

即把所有 $T_i$ 按下标从小到大依次拼接起来。

例如，当 $k=3$，且 $s_0=\texttt{a},s_1=\texttt{b},s_2=\texttt{c}$ 时：

$$T_0=\texttt{a},\quad T_1=\texttt{ab},\quad T_2=\texttt{abc},\quad T_3=\texttt{abca},$$$$T_7=\texttt{abcabcab},$$

并且

S = aababcabcaabcab...

记 $S_n$ 为 $S$ 的长度为 $n$ 的前缀。

给定 $n,k$，请计算在字母表大小为 $k$ 时，字符串 $S_n$ 中不同的非空子串数量。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行包含两个整数 $n_i,k_i$，表示一组询问中的前缀长度和字母表大小。

输出格式

输出 $T$ 行，第 $i$ 行输出第 $i$ 组询问的答案。

数据范围

• $1\le T\le 10^5$；
• $1\le n_i\le 10^9$；
• $1\le k_i\le 10^9$。

样例

输入

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

输出

1
2
5
8
11
17
23