Số thú vị

Bình là người đam mê Toán học và thích tìm hiểu về các số có tính chất đặc biệt. Bình gọi số nguyên dương \(X\) là số thú vị nếu hai chữ số tận cùng của \(X\) tạo thành một số chia hết cho số nguyên dương \(k\) cho trước.

Ví dụ, nếu \(k = 12\) thì số \(1236\) là số thú vị vì hai chữ số cuối của nó là \(36\), mà \(36\) chia hết cho \(12\). Ngược lại, số \(1457\) không phải là số thú vị.

Bình muốn đếm số lượng số thú vị trong mỗi đoạn \([a, b]\).

Yêu cầu. Với mỗi truy vấn, hãy đưa ra số lượng số thú vị trong đoạn \([a, b]\).

Input

• Dòng đầu tiên chứa hai số nguyên \(T\) và \(k\) (\(T \le 10^5\), \(1 \le k < 100\)).
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a, b\) (\(10^2 \le a \le b \le 10^{18}\)).

Output

Ghi ra tệp văn bản gồm \(T\) dòng, mỗi dòng là số lượng số thú vị trong đoạn tương ứng.

Input

%
2 11
100 200
201 300

Output

%
11
10

Scoring

• (50%) \(T = 1\), \(10^2 \le a \le b \le 10^6\).
• (40%) \(T \le 10^5\), \(10^2 \le a \le b \le 10^6\).
• (10%) \(T \le 10^5\), \(10^2 \le a \le b \le 10^{18}\).