k-mükəmməl ədədlər

Bir ədəd, özündən başqa bütün müsbət bölənlərinin cəminə bərabərdirsə, mükəmməl adlanır. Məsələn, ilk mükəmməl ədəd 6 = 1 + 2 + 3-dür. İndi bunu daha dəqiq ifadə edək və aşağıdakı funksiyanı nəzərdən keçirək:

Ədəd yalnız σ(n) - n = 0 olduqda mükəmməldir.

Ədədi k-mükəmməl adlandıraq, əgər |σ(n) - n| = k. Məsələn, 2-mükəmməl ədədlər 3 və 10-dur. Sizin vəzifəniz [l, r] intervalında k-mükəmməl ədədlərin sayını tapmaqdır.

Giriş verilənləri

Giriş faylının ilk sətirində testlərin sayı t (1 ≤ t ≤ 100000) verilir. Hər bir test bir sətirdən ibarətdir və boşluqla ayrılmış üç tam ədəd l, r və k ehtiva edir (1 ≤ l ≤ r ≤ 10^6, 0 ≤ k ≤ 10^9).

Çıxış verilənləri

Hər bir test üçün [l, r] intervalında k-mükəmməl ədədlərin sayını ehtiva edən bir sətir çıxarın.

Nümunələr