Məsələlər
k-совершенные числа
k-совершенные числа
Известно, что число называется совершенным, если оно равно сумме всех своих положительных делителей, кроме его самого. Например, первое совершенное число -- \textbf{6 = 1 + 2 + 3}. Теперь сформулируем это более строго, рассмотрим функцию:
\includegraphics{https://static.e-olymp.com/content/9a/9a0eb405326f047983fb4f3ba4d68cc201bca30f.jpg}
Число является совершенным тогда и только тогда, когда \textbf{σ(n) -- n = 0}.
Назовем число \textbf{k}-совершенным, если \textbf{|σ(n) -- n| = k}. Таким образом \textbf{2}-совершенными числами будут, например, \textbf{3} и \textbf{10}. Ваша задача найти количество \textbf{k}-совершенных чисел на отрезке \textbf{\[l, r\]}.
\InputFile
В первой строке входного файла задано количество тестов \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{100000}). Каждый тест состоит из одной строки, содержащей три целых числа \textbf{l}, \textbf{r} и \textbf{k}, разделенных одним пробелом (\textbf{1} ≤ \textbf{l} ≤ \textbf{r} ≤ \textbf{10^6}, \textbf{0} ≤ \textbf{k} ≤ \textbf{10^9}).
\OutputFile
Для каждого теста выведите строку, содержащую количество \textbf{k}-совершенных чисел на отрезке \textbf{\[l, r\]}.
Giriş verilənləri #1
3 1 10 2 1 10 0 36 100 4
Çıxış verilənləri #1
2 1 3