题目描述

训练营操场上画了一条很长的格子跑道，每个格子都有一个编号。

小明玩跳格子游戏时，有一个习惯：如果这次选择的数字是 k，那么他只会踩编号是 k 的倍数的格子。

老师给出了 q 次游戏记录。每次记录包含三个整数 l、r、k，表示小明只观察编号从 l 到 r 的这段格子，并且只会踩其中编号是 k 的倍数的格子。

请你计算每次游戏中，小明会踩到多少个格子。

输入格式

第一行输入一个整数 q，表示游戏记录数量。

接下来 q 行，每行输入三个整数 l、r、k。

输出格式

对于每次游戏，输出一行一个整数，表示小明会踩到的格子数量。

样例

3
1 10 3
5 20 4
7 7 7

3
4
1

样例说明

第 1 次游戏中，1 到 10 之间 3 的倍数有：

3, 6, 9

所以答案是 3。

第 2 次游戏中，5 到 20 之间 4 的倍数有：

8, 12, 16, 20

所以答案是 4。

数据范围

$1 <= q <= 2\times 10^5$

$1 <= l <= r <= 10^{12}$

$1 <= k <= 10^{12}$

测试点说明

• 测试点 1 ~ 12：$q <= 100$，且 $r - l <= 5000$
• 测试点 13 ~ 20：$q <= 2\times 10^5$，$1 <= l <= r <= 10^{12}$