Trong toán học, ước của một số ~n~ là các số ~m~ mà ~n~ chia hết cho ~m~. Tổng ước số thực sự của một số ~n~ là tổng tất cả các số nguyên dương ~m < n~ mà ~m~ là ước của ~n~. Trong bài này, ta định nghĩa tổng ước số gần thực sự của một số ~n~ là tổng tất cả các số nguyên dương ~m < n~ mà ~n~ chia ~m~ có số dư không vượt qua một hằng số ~k~ cho trước. Cho ~Q~ truy vấn, truy vấn thứ ~i~ gồm hai số nguyên dương ~l_i~ và ~r_i~, với mỗi truy vấn, hãy tính tổng các tổng ước số gần thực sự của các số trong khoảng từ ~l_i~ tới ~r_i~.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên không âm ~q~ và ~k~.
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~l_i~ và ~r_i~ ~(l_i \leq r_i)~.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là câu trả lời cho truy vấn thứ ~i~.

Sample input

2 1
2 5
1 1

Sample output

17
0

Giải thích

• Tổng các ước số gần thực sự của các số từ ~1~ tới ~5~ lần lượt là ~0, 1, 3, 6, 7~

Giới hạn

• 20% số test có ~q, k, l_i, r_i \leq 100~
• 20% số test có ~q \leq 10^6, k, l_i, r_i \leq 5000~
• 30% số test có ~q \leq 10^6, l_i, r_i \leq 10^6, k = 0~
• 30% số test có ~q \leq 10^6, k, l_i, r_i \leq 10^6~