Ortaq böləni olmayan#2725
Verilən N ədədinə əsasən, A və B arasında, daxil olmaqla, N ilə nisbi sadə olan tam ədədlərin sayını hesablamaq tələb olunur.
İki tam ədəd yalnız 1 olan ümumi müsbət bölənləri yoxdursa və ya başqa sözlə, onların ən böyük ortaq böləni 1 olarsa, nisbi sadə hesab olunur. 1 hər bir tam ədədə nisbi sadədir.
Birinci sətirdə T (0 < T \leq 100) — test hallarının sayı verilir. Növbəti T sətirdə hər birində üç tam ədəd: A, B, N verilir; burada 1 \leq A \leq B \leq 10^{15} və 1 \leq N \leq 10^9.
Hər bir test halı üçün, A və B arasında, daxil olmaqla, N ilə nisbi sadə olan tam ədədlərin sayını göstərin. Aşağıdakı çıxış formatına əməl edin.
Nümunə 1