במעבדה לתורת המספרים של אוניברסיטה חוקרים את הקשר בין התפלגות הריבועים והקוביות של מספרים שלמים חיוביים.

יהי $k$ מספר שלם אי־שלילי. נבחן את קבוצת המספרים השלמים החיוביים מ־$a$ עד $b$, כולל הקצוות. צפיפותה מסדר $k$ היא מספר הזוגות של מספרים שלמים חיוביים $x,y$ המקיימים $a \le x^2 \le b$, $a \le y^3 \le b$ וכן $|x^2-y^3| \le k$.

למשל, הצפיפות מסדר $2$ של קבוצת המספרים השלמים החיוביים מ־$1$ עד $30$ היא $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$, מחשבת את הצפיפות מסדר $k$ של קבוצת המספרים השלמים החיוביים מ־$a$ עד $b$, כולל הקצוות.

קלט

הקלט מכיל שלוש שורות. הראשונה מכילה את המספר השלם החיובי $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

תתי־משימות

נקודות לתת־משימה מוענקות רק אם כל הבדיקות שלה ושל תתי־המשימות הנדרשות עברו בהצלחה.