Sau khi băng qua cây cầu treo, BabyOrange và hoangks7 tìm thấy được rương kho báu, mỗi tội... nó bị khóa :(
BabyOrange đột nhiên thấy có gợi ý trên rương, nhờ gợi ý, cả hai người mới biết mật mã là số lượng các "Số Hạnh Phúc" trong khoảng từ \(L\) đến \(R\). Nhiệm vụ của bạn là tìm mật mã cho chiếc rương kho báu đó.
Một số được gọi là "Số Hạnh Phúc" nếu:

• Tổng các chữ số là một số nguyên tố
• Bản thân số đó chia hết cho \(K\)

Input

• Một dòng chứa 3 số nguyên \(L\), \(R\), \(K\)
• \(1 \le L \le R \le 10^{18}\), \(1 \le K \le 100\)

Output

• Một dòng chứa một số là số lượng "Số Hạnh Phúc"

Example

10 20 2

4