يدرس مختبر نظرية الأعداد في إحدى الجامعات العلاقة بين توزيع مربعات الأعداد الصحيحة الموجبة ومكعباتها.

ليكن $k$ عدداً صحيحاً غير سالب. نعتبر مجموعة الأعداد الصحيحة الموجبة من $a$ إلى $b$، مع شمول الطرفين. نعرّف كثافة هذه المجموعة من الرتبة $k$ بأنها عدد أزواج الأعداد الصحيحة الموجبة $x$ و$y$ التي تحقق $a \le x^2 \le b$ و$a \le y^3 \le b$ و$|x^2-y^3| \le k$.

مثلاً، كثافة مجموعة الأعداد الصحيحة الموجبة من $1$ إلى $30$ من الرتبة $2$ تساوي $3$، لأن الأزواج التالية تحقق الشروط:

• $x=1$, $y=1$, $|x^2-y^3|=|1-1|=0$;

• $x=3$, $y=2$, $|x^2-y^3|=|9-8|=1$;

• $x=5$, $y=3$, $|x^2-y^3|=|25-27|=2$.

اكتب برنامجاً يحدد كثافة مجموعة الأعداد الصحيحة الموجبة من $a$ إلى $b$، مع شمول الطرفين، من الرتبة $k$، عند إعطائه العددين الصحيحين الموجبين $a$ و$b$ والعدد الصحيح غير السالب $k$.

الإدخال

يتكون الإدخال من ثلاثة أسطر. يحتوي الأول على العدد الصحيح الموجب $a$، والثاني على العدد الصحيح الموجب $b$، والثالث على العدد الصحيح غير السالب $k$ ($1 \le a \le b \le 10^{18}$، $0 \le k \le 10^{18}$).

الإخراج

أخرج عدداً صحيحاً واحداً: الكثافة المطلوبة من الرتبة $k$ لمجموعة الأعداد الصحيحة الموجبة من $a$ إلى $b$، مع شمول الطرفين.

أمثلة

الإدخال 1

1
30
2

الإخراج 1

3

المهام الفرعية

تُمنح نقاط كل مهمة فرعية فقط عند اجتياز جميع اختبارات تلك المهمة والمهام الفرعية المطلوبة لها.