【题目描述】

小灰灰最近迷上了数字游戏。

游戏是这样的，给定正整数 $x$ 和大于 1 的正整数 $k$，他需要把 $x$ 变为 1，通过以下两种操作：

• 如果当前的 $x$ 是 $k$ 的倍数，那么将 $x$ 除去 $k$；
• 如果当前的 $x$ 不是 $k$ 的倍数，那么将 $x$ 加上 1。

能够发现，经过若干次操作后 $x$ 终将会变为 1，而这里的操作次数很值得研究。

于是记 $f(x, k)$ 表示将 $x$ 在除 $k$ 和加 1 的方式下变为 1 的最少操作次数。

小蓝观察了这个函数，于是向你提出了 $m$ 个问题，其中第 $i$ 个问题给定三个参数 $l_i$、$r_i$ 和 $k_i$，你需要计算出区间 $[l_i, r_i]$ 中所有整数在除 $k_i$ 和加 1 的方式下变为 1 的最少操作次数，并求和输出。

形式化的说，对于第 $i$ 个问题，你需要输出 $\sum_{j=l_i}^{r_i} f(j, k_i)$。

---

【输入描述】

输入第一行一个整数 $m$ 代表询问次数

接下来 $m$ 行，每行三个空格分隔的整数 $l_i$、$r_i$ 和 $k_i$

保证：

• $1\le m \le 10^5$
• $1\le l_i \le r_i \le 10^{9}$
• $2\le k_i \le 10^9$

---

【输出描述】

输出共 $m$ 行，第 $i$ 行一个整数表示第 $i$ 次询问的答案。

---

【样例 1】

【样例 1 输入】

1
1 10 2

【样例 1 输出】

35

【样例 1 解释】

$k=2$ 时，每个数的操作次数：

• $f(1,2)=0$（已是1，无需操作）
• $f(2,2)=1$（$2/2=1$）
• $f(3,2)=3$（$3+1=4$，$4/2=2$，$2/2=1$）
• $f(4,2)=2$（$4/2=2$，$2/2=1$）
• $f(5,2)=5$（$5+1=6$，$6/2=3$，$3+1=4$，$4/2=2$，$2/2=1$）
• $f(6,2)=4$（$6/2=3$，$3+1=4$，$4/2=2$，$2/2=1$）
• $f(7,2)=4$（$7+1=8$，$8/2=4$，$4/2=2$，$2/2=1$）
• $f(8,2)=3$（$8/2=4$，$4/2=2$，$2/2=1$）
• $f(9,2)=7$（$9+1=10$，$10/2=5$，$5+1=6$，$6/2=3$，$3+1=4$，$4/2=2$，$2/2=1$）
• $f(10,2)=6$（$10/2=5$，$5+1=6$，$6/2=3$，$3+1=4$，$4/2=2$，$2/2=1$）

总和 = $0+1+3+2+5+4+4+3+7+6=35$

【样例 2】

【样例 2 输入】

3
1 5 3
6 6 3
1 1 5

【样例 2 输出】

12
3
0

【样例 2 解释】

第一个询问 $[1,5], k=3$：

• $f(1,3)=0$

• $f(2,3)=2$（$2+1=3$，$3/3=1$）

• $f(3,3)=1$（$3/3=1$）

• $f(4,3)=5$（$4+2=6$，$6/3=2$，$2+1=3$，$3/3=1$）

• $f(5,3)=4$（$5+1=6$，$6/3=2$，$2+1=3$，$3/3=1$）

  总和 = $0+2+1+5+4=12$

第二个询问 $[6,6], k=3$：

• $f(6,3)=3$（$6/3=2$，$2+1=3$，$3/3=1$）

  总和 = $3$

第三个询问 $[1,1], k=5$：

• $f(1,5)=0$（已是1，无需操作）

  总和 = $0$

【样例 3】

【样例 3 输入】

5
7 7 7
1 4 3
10 10 2
9 9 3
8 8 2

【样例 3 输出】

1
8
6
2
3

【样例 3 解释】

第一个询问 $[7,7], k=7$：

• $f(7,7)=1$（$7/7=1$）

  总和 = $1$

第二个询问 $[1,4], k=3$：

• $f(1,3)=0$

• $f(2,3)=2$（$2+1=3$，$3/3=1$）

• $f(3,3)=1$（$3/3=1$）

• $f(4,3)=5$（$4+2=6$，$6/3=2$，$2+1=3$，$3/3=1$）

  总和 = $0+2+1+5=8$

第三个询问 $[10,10], k=2$：

• $f(10,2)=6$（$10/2=5$，$5+1=6$，$6/2=3$，$3+1=4$，$4/2=2$，$2/2=1$）

  总和 = $6$

第四个询问 $[9,9], k=3$：

• $f(9,3)=2$（$9/3=3$，$3/3=1$）

  总和 = $2$

第五个询问 $[8,8], k=2$：

• $f(8,2)=3$（$8/2=4$，$4/2=2$，$2/2=1$）

  总和 = $3$

---

【数据规模与约定】

测试点编号	分数	特殊性质 1	特殊性质 2
1	5	$l = r$	$k \le 9$
2	5·		无
3	10	$r \le 2\times 10^7$	$k = 3$
4	15	$r \le 1000$ 且 $m \le 1000$	$k\le 9$
5	5	无	$k = 10^9$
6	15	$r \le 1000$ 且 $m \le 1000$	无
7	25	无	$k \le 9$
8	20		无