Đèn nháy

Nhân dịp mở cửa trở lại phố đi bộ Ninh Bình sau dịch Covid-19, ban tổ chức đã trang trí phố đi bộ bằng $1$ dây đèn nháy có $n$ bóng đèn được đánh số từ $1$ đến $n$. Các đèn nháy được lập trình điều khiển lần lượt thay đổi trạng thái theo quy tắc sau:

• Lần $1$: Thay đổi trạng thái các bóng đèn có số thứ tự chia hết cho $1$.
• Lần $2$: Thay đổi trạng thái các bóng đèn có số thứ tự chia hết cho $2$.
• Lần $3$: Thay đổi trạng thái các bóng đèn có số thứ tự chia hết cho $3$.
• ...
• Lần $n$: Thay đổi trạng thái các bóng đèn có số thứ tự chia hết cho $n$.

Biết rằng ban đầu tất cả các bóng đèn đều tắt. Khi thay đổi trạng thái, các bóng đèn chuyển từ bật sang tắt hoặc tắt sang bật.

Yêu cầu: Hãy cho biết sau $n$ lần thay đổi trạng thái thì từ bóng đèn $p$ đến bóng đèn $q$ (tính cả hai bóng $p$ và $q$) có bao nhiêu bóng đèn đang bật?

Dữ liệu vào

Một dòng chứa ba số nguyên $p,q,n$ ($1\le p<q\le n\le {10}^{18}$).

Dữ liệu ra

In ra số lượng bóng đèn đang bật trong các bóng từ $p$ đến $q$.

Ràng buộc

• $1\le p<q\le n\le {10}^{18}$.

Subtasks

• $40\%$ số test có $n\le 3000$.
• $40\%$ số test có ${10}^4\le n\le {10}^5$.
• $20\%$ số test có ${10}^7<n\le {10}^{18}$.

Ví dụ