题目描述

蒜头君定义了一种数叫 suan 数，如果一个数 $x$ 是 suan 数，那么它必定能被 $k$ 整除，每次给定一个区间 $(l,r]$，保证 $l < r$，求该区间中有多少个数是 suan 数，其中 $k$ 为给定的数。

输入格式

第一行两个正整数 $n,k$，表示有 $n$ 个询问，$k$ 意义见题面。

接下来 $n$ 行，每行两个正整数 $l,r$，表示一个询问。

输出格式

对于每一个询问，输出一行，表示答案。

样例

输入样例1：

3 5

1 1

1 10

3 15

输出样例1：

0

2

3

样例解释1：

在该样例中，$5,10,15,20,...$ 为 suan 数。

数据范围与提示