Ortaq böləni olmayan

Verilən N ədədinə əsasən, sizdə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ə və ya sadə deyilir. 1 hər bir tam ədədə nisbi sadədir.

Giriş verilənləri

Girişin ilk sətri T (0 < T ≤ 100) test halları sayını ehtiva edir. Növbəti T sətrin hər biri üç tam ədəd A, B, N ehtiva edir, burada (1 ≤ A ≤ B ≤ 10^15) və (1 ≤ N ≤ 10^9).

Çıxış verilənləri

Hər bir test halı üçün, A və B arasında, daxil olmaqla, N ilə nisbi sadə olan tam ədədlərin sayını çap edin. Aşağıdakı çıxış formatına əməl edin.

Nümunələr