Cho một số tự nhiên \(a\), ta gọi số ước của \(a\) là số lượng các số tự nhiên b khác nhau mà \(a\) chia hết cho \(b\). Ví dụ: \(a = 4\) thì tập hợp các ước của \(4\) là \({1,2,4}\), ta nói số \(4\) là số có \(3\) ước.

Bài toán đếm ước đã từ lâu là bài toán cơ bản mà bất kì học sinh nào cũng phải học. Hôm nay thầy giáo yêu cầu như sau: Cho trước \(3\) số tự nhiên \(L, R, K\). Hãy đếm số lượng số tự nhiên thuộc đoạn \([L, R]\) mà có đúng \(K\) ước.

Dữ liệu vào:

• Một dòng gồm \(3\) số \(L, R, K\) \((2 \le L \le R \le 10^{12}, 2 \le K \le 10^{12})\).

Dữ liệu ra:

• Ghi ra số lượng số tự nhiên thuộc \([L, R]\) mà có đúng \(K\) ước.

Input 1

1 10 2

Output 1

4

Giải thích

• Có \(4\) số có \(2\) ước trong đoạn \([1,10]\) là \(2,3,5,7\)

Ràng buộc:

• Có 20% số test tương ứng 20% số điểm có \(K = 2; 2 \le L \le R \le 10^7.\)
• Có 20% số test tương ứng 20% số điểm có \(K = 3; 2 \le L \le R \le 10^7.\)
• Có 20% số test tương ứng 20% số điểm có \(K = 4; 2 \le L \le R \le 10^7.\)
• Có 20% số test tương ứng 20% số điểm có \(K\) là số nguyên tố; \(2 \le L \le R \le 10^7.\)
• Có 20% số test tương ứng 20% số điểm có \(K\) bất kì; \(2 \le L \le R \le 10^{12}\).