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 một 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 bị 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 thứ \(p\) đến bóng đèn thứ \(q\) có bao nhiêu bóng đèn đang bật?

Dữ liệu vào: 

+ Ghi ba số nguyên \(p,\ q,\ n\ (1 \leq p < \ q \leq \ n \leq 10^{18})\).

Kết quả: 

+ Ghi số lượng bóng đèn bật.

Ví dụ:

Ràng buộc:

+ 40% test có \(n\ \leq \ 3000\);

+ 40% test có \(10^{4} \leq n \leq \ 10^{5}\);

+ 20% test có \(10^{7}\ \leq \ n\ \leq \ 10^{18}\)_;