Với số nguyên dương ~X~, gọi hai chữ số tận cùng của ~X~ là ~X \bmod 100~. Cho số ~k~ và ~T~ truy vấn, mỗi truy vấn là đoạn ~[a,b]~.

Yêu cầu

Đếm số lượng số ~X~ trong đoạn ~[a,b]~ sao cho ~X \bmod 100~ chia hết cho ~k~.

Input

Dòng đầu chứa hai số ~T,k~ ~(1 \le T \le 10^5, 1 \le k \le 99)~.

~T~ dòng tiếp theo, mỗi dòng chứa hai số ~a,b~ ~(10^2 \le a \le b \le 10^{18})~.

Output

In ra đáp án cho mỗi truy vấn trên một dòng.

Subtask

• Subtask 1: ~T=1~, ~10^2 \le a \le b \le 10^6~.
• Subtask 2: ~T \le 10^5~, ~10^2 \le a \le b \le 10^6~.
• Subtask 3: ~T \le 10^5~, ~10^2 \le a \le b \le 10^{18}~.

Ví dụ

3 3
100 100
100 105
100 120

1
2
7