Daha bir yeni funksiya

Funksiya ϕ(n) və ya phi(n), həmçinin Eyler funksiyası adlanır, və n-dən kiçik və ya bərabər olan, n ilə qarşılıqlı sadə (yəni ümumi böləni olmayan) müsbət tam ədədlərin sayını müəyyən edir. Burada 1 bütün ədədlərlə qarşılıqlı sadə hesab olunur. Məsələn, 24 ilə qarşılıqlı sadə olan səkkiz ədəd var (1, 5, 7, 11, 13, 17, 19 və 23), buna görə də ϕ(24) = 8.

Bir ədədin phi dərinliyi, 1 əldə etmək üçün yerinə yetirilməli olan addımların sayıdır. Misala baxaq:

• ϕ(13) = 12 . . . addım 1

• ϕ(12) = 4 . . . addım 2

• ϕ(4) = 2 . . . addım 3

• ϕ(2) = 1 . . . addım 4

Beləliklə, phi(13) dərinliyi 4-ə bərabərdir. Bu funksiyanı depthphi adlandıraq. Beləliklə, depthphi(13) = 4 yazmaq olar. depthphi funksiyasının cəmi (SODF) iki tam ədəd arqument kimi qəbul edir və aşağıdakı kimi müəyyən edilir:

Verilmiş m və n ədədləri üçün SODF(m, n) dəyərini hesablayın.

Giriş məlumatları

Birinci sətir n (0 < n < 2001) tam ədədini ehtiva edir, bu, testlərin sayını göstərir. Növbəti n sətirin hər biri iki tam ədəd m və n (2 ≤ m ≤ n ≤ 2000000) ehtiva edir.

Çıxış məlumatları

Hər bir test üçün ayrıca sətirdə bir tam ədəd - SODF(m, n) dəyərini çıxarın.